home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / ADVTUT.TXT < prev    next >
Text File  |  1992-12-08  |  93KB  |  3,907 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.                  PCCTS Version 1.0x Advanced Tutorial
  8.  
  9.  
  10.                  Terence Parr, Hank Dietz, Will Cohen
  11.  
  12.                    School of Electrical Engineering
  13.                           Purdue University
  14.                       West Lafayette, IN  47907
  15.                              Spring 1992
  16.                          parrt@ecn.purdue.edu
  17.                          hankd@ecn.purdue.edu
  18.                         cohenw@ecn.purdue.edu
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.      Constructing a translator can be viewed as an  iterative  refine-
  27. ment  process  moving  from  language recognition to intermediate-form
  28. transformation.  This  document  presents  one  possible  sequence  of
  29. refinements.   We shall use as many features of PCCTS as is reasonable
  30. without regards to optimality.
  31.  
  32.      We will develop a  compiler  for  a  simple  string  manipulation
  33. language  called  sc.   The  compiler  will generate code for a simple
  34. stack machine.
  35.  
  36.      This document assumes familiarity with the concept  of  a  parser
  37. generator  and  other  language  recognition  tools - in particular, a
  38. passing familiarity with YACC is useful.
  39.  
  40.      The development will proceed as follows:
  41.  
  42. (i)  Define a grammar to  recognize  functions,  statements,  variable
  43.      definitions and expressions in sc.
  44.  
  45. (ii) Add symbol table management to the grammar developed in (i)
  46.  
  47. (iii)Add actions to translate sc into stack code for  a  simple  stack
  48.      machine.
  49.  
  50. (iv) Construct trees as an intermediate-form.
  51.  
  52. (v)  Build a code-generator to translate the trees into  executable  C
  53.      code.
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.                                                                 Page 1
  62.  
  63. PCCTS Advanced Tutorial 1.0x
  64.  
  65.  
  66. 1.  sc Language definition
  67.  
  68.      sc is a simple, C-like language with only one data  object  type-
  69. string.  It has global variables, functions, arguments and local vari-
  70. ables.  There are no arrays or structures.
  71.  
  72. 1.1.  sc Expressions
  73.  
  74.      Expression atoms  are  limited  to  variables,  string  constants
  75. ("character(s)") and function calls (function(expr)).  The string con-
  76. stants "false" or "0" represent false and true or "1" represent  true.
  77. A  limited set of operators are available (from highest to lowest pre-
  78. cedence)
  79.  
  80. -       Unary operator negate. Numeric operator.
  81.  
  82. *, /    Binary operators multiply and divide.   Groups  left-to-right.
  83.         Numeric operator.
  84.  
  85. +, -    Binary operators  add  and  subtract.   Groups  left-to-right.
  86.         Numeric operator except for + which is "concatenate" if one of
  87.         operands is non-numeric.
  88.  
  89. ==, !=  Binary operators  equal,  not  equal.   Groups  left-to-right.
  90.         Numeric or non-numeric.
  91.  
  92. =       Binary assignment operator.  Groups right-to-left.  For  exam-
  93.         ple, a = b = c means to assign c to b and then to a.
  94.  
  95.  
  96. 1.2.  sc Functions and statements
  97.  
  98.      Functions may have multiple local  variables,  but  at  most  one
  99. parameter.   All  functions  implicitly return a string to the calling
  100. function, although the value need not be used.  If a  return-statement
  101. is  not executed within a function, the return value for that function
  102. is undefined.  Functions are defined exactly as in C:
  103.  
  104.  
  105. function(arg)
  106. {
  107.         statement(s)
  108. }
  109.  
  110.  
  111.  
  112.      A function called main() must exist so that our  interpreter  and
  113. compiled code knows where to begin execution.  Also, main() always has
  114. a implicitly passed parameter which contains  any  command-line  argu-
  115. ment.
  116.  
  117.      sc has six statements.
  118.  
  119. if   Conditionals have the form:
  120.  
  121.  
  122.  
  123.                                                                 Page 2
  124.  
  125. PCCTS Advanced Tutorial 1.0x
  126.  
  127.  
  128.  
  129.      if ( expr ) statement
  130.  
  131.  
  132.  
  133. whileLoops have the form:
  134.  
  135.  
  136.      while ( expr ) statement
  137.  
  138.  
  139.  
  140. { statement(s) }
  141.      Block statements treat more than one statement as a single state-
  142.      ment  as  in  C.  However, one cannot define variables local to a
  143.      block statement.
  144.  
  145. expr;An expr can include any valid sc expression, but only expressions
  146.      involving assignments and function calls are useful.
  147.  
  148. return expr ;
  149.      This statement behaves exactly like the C return statement except
  150.      that only strings can be returned.
  151.  
  152. print expr;
  153.      Print the string described by expr to stdout.
  154.  
  155. 1.3.  Example
  156.  
  157.      The following code is a simple sc program that  computes  n  fac-
  158. torial.
  159.  
  160.  
  161. main(n)
  162. {
  163.         print fact(n);
  164.         print "\n";
  165. }
  166.  
  167. fact(n)
  168. {
  169.         if ( n == "0" ) return "1";
  170.         return n * fact(n - "1");
  171. }
  172.  
  173.  
  174.  
  175. 2.  Language recognition
  176.  
  177.      We begin our project by constructing a parser-a program that will
  178. recognize  phrases  in  sc.  The first two subsections describe the sc
  179. lexicon while the later subsections present the sc  grammar  with  and
  180. without symbol table management.
  181.  
  182.  
  183.  
  184.  
  185.                                                                 Page 3
  186.  
  187. PCCTS Advanced Tutorial 1.0x
  188.  
  189.  
  190. 2.1.  Lexical analysis
  191.  
  192.      Our language has only strings of upper- and  lower-case  letters,
  193. called  WORD's,  operators,  string  constants  and  a few grammatical
  194. grouping symbols; all of which except WORD will be defined  implicitly
  195. by  mentioning  them  in the grammar.  WORD will be placed last in the
  196. grammar-i.e. after all keywords have been defined.  Since keywords are
  197. really  just  strings of characters as well, they must be treated spe-
  198. cially.  When two (or more) regular expressions can be matched for the
  199. current input text, DLG scanners resolve the ambiguity by matching the
  200. input to the expression mentioned first in the description.  Hence, we
  201. place
  202.  
  203.  
  204. #token WORD "[a-zA-Z]+"
  205.  
  206.  
  207.  
  208. at the bottom of the file.
  209.  
  210.      Tabs, blanks and carriage-returns are all considered white  space
  211. and  are  to be ignored (although we wish to track line numbers).  The
  212. following ANTLR code will instruct  the  parser  to  skip  over  white
  213. space.
  214.  
  215.  
  216. #token "[\t\ ]+"   << zzskip(); >>         /* Ignore White */
  217. #token "\n"        << zzline++; zzskip(); >>
  218.  
  219.  
  220.  
  221.      Strings are strings of characters enclosed in double-quotes.  For
  222. simplicity  we will allow any character not in the ASCII range 0..0x1F
  223. (hex) plus any "escaped" version of the same character set.
  224.  
  225.  
  226. #token STRING       "\"(~[\0-\0x1f\"\\]|(\\~[\0-\0x1f]))*\"" <<;>>
  227.  
  228.  
  229.  
  230. 2.2.  Attributes
  231.  
  232.      The DLG scanner matches keywords, WORD's,  etc...  on  the  input
  233. stream.   The  way ANTLR parsers access that text is though the attri-
  234. bute mechanism.  Attributes are run-time objects associated  will  all
  235. grammar  elements (items to the right of the :  in a rule definition).
  236. Although attributes are associated with subrules and rule  references,
  237. only  those attributes linked to grammar tokens are of interest to us.
  238. Attributes are denoted $i where i is the grammar element  i  positions
  239. from  the start of the alternative.  The user must define an attribute
  240. type called Attrib.  This type is  most  often  some  sort  of  string
  241. whether  constant or dynamically allocated.  For simplicity, we employ
  242. a standard attribute type available with the PCCTS system.  Attributes
  243. are  structures  that  contain a constant width (30 character) string.
  244.  
  245.  
  246.  
  247.                                                                 Page 4
  248.  
  249. PCCTS Advanced Tutorial 1.0x
  250.  
  251.  
  252. By placing the character array  inside  of  a  structure,  the  entire
  253. string  can be copied like any simple C variable.  The ANTLR pseudo-op
  254. #header is used to describe attributes and other information that must
  255. be  present  in all generated C files.  In our case, we simply need to
  256. include the standard text attribute definition.  This  pseudo-op  must
  257. occur first in the grammar file if it exists at all.
  258.  
  259.  
  260. #header <<#include "charbuf.h">>
  261.  
  262.  
  263.  
  264. 2.3.  Grammatical analysis
  265.  
  266.      This subsection describes the grammatical or syntactic aspects of
  267. sc.   No  symbol  table management is used and therefore functions and
  268. variables are considered simple WORD's.  Later versions of the grammar
  269. can use the tokens VAR and FUNC.
  270.  
  271. 2.3.1.  Definitions, variables
  272.  
  273.      An sc program is a sequence  of  definitions-variables  or  func-
  274. tions:
  275.  
  276.  
  277. p       :   ( func | "var" def ";" )* ;
  278.  
  279.  
  280.  
  281. The ( )* subrule means that there are zero or more definitions.  The |
  282. operator starts a new alternative.
  283.  
  284.      The grammar for a variable definitions is broken up  between  the
  285. rule p and def so that def can be reused for parameter definitions (it
  286. also makes more sense when code generation has been added).
  287.  
  288.  
  289. def     :   WORD ;
  290.  
  291.  
  292.  
  293. 2.3.2.  Functions
  294.  
  295.      sc functions follow C's format except  that  the  default  return
  296. type is a string instead of int.
  297.  
  298.  
  299. func    :   WORD "\(" { WORD } "\)"
  300.             "\{"
  301.                 ( def )*
  302.                 ( statement )*
  303.             "\}"
  304.         ;
  305.  
  306.  
  307.  
  308.  
  309.                                                                 Page 5
  310.  
  311. PCCTS Advanced Tutorial 1.0x
  312.  
  313.  
  314. Note that the parentheses and the curly-braces must be escaped with  \
  315. because they are special regular expression symbols.
  316.  
  317. 2.3.3.  Statements
  318.  
  319.      The statements outlined in the  sc  language  definition  can  be
  320. described with
  321.  
  322.  
  323. statement
  324.         :   expr ";"
  325.         |   "\{" ( statement )* "\}"
  326.         |   "if" "\(" expr "\)" statement {"else" statement}
  327.         |   "while" "\(" expr "\)" statement
  328.         |   "return" expr ";"
  329.         |   "print" expr ";"
  330.         ;
  331.  
  332.  
  333.  
  334. where { } means optional.
  335.  
  336. 2.3.4.  Expressions
  337.  
  338.      The operators and expression  atoms  described  in  the  language
  339. definition can be recognized by the following grammar fragment.
  340.  
  341.  
  342. expr    :   WORD "=" expr
  343.         |   expr0
  344.         ;
  345.  
  346. expr0   :   expr1 ( ("=="|"!=") expr1 )*
  347.         ;
  348.  
  349. expr1   :   expr2 ( ("\+"|"\-") expr2 )*
  350.         ;
  351.  
  352. expr2   :   expr3 ( ("\*"|"/") expr3 )*
  353.         ;
  354.  
  355. expr3   :   {"\-"} expr4
  356.         ;
  357.  
  358. expr4   :   STRING
  359.         |   WORD { "\(" { expr } "\)" }
  360.         |   "\(" expr "\)"
  361.         ;
  362.  
  363.  
  364.  
  365. Rule expr is ambiguous if we only look one token into the future since
  366. WORD  can  also be an expr0.  However, if we were to tell ANTLR to use
  367. two tokens, it could see that the  "="  assignment  operator  uniquely
  368.  
  369.  
  370.  
  371.                                                                 Page 6
  372.  
  373. PCCTS Advanced Tutorial 1.0x
  374.  
  375.  
  376. identifies  which alternative to match when WORD is the first token of
  377. lookahead.  Rule expr makes this grammar LL(2); but, we only  use  the
  378. extra  token  of lookahead in expr (leaving all others LL(1)).  Please
  379. note the use of ANTLR's command-line option "-k 2"  in  the  makefiles
  380. presented below.
  381.  
  382.      ANTLR does not have a method  of  explicitly  outlining  operator
  383. precedence.   Instead  precedence  is  implicitly  defined by the rule
  384. invocation sequence or abstractly by the parse-tree.  Rule expr  calls
  385. expr0 which calls expr1 etc... nesting more and more deeply.  The pre-
  386. cedence rule-of-thumb in ANTLR (and any LL-type parser) is: the deeper
  387. the  nesting  level,  the  higher the precedence (the more tightly the
  388. operator binds).  Operators in the expression starting rule  have  the
  389. lowest precedence whereas operators in the last rule in the expression
  390. recursion have the highest precedence.  This becomes  obvious  when  a
  391. parse-tree for some input text is examined.
  392.  
  393.      Once again, note that the operators for sc  must  be  escaped  as
  394. they are reserved regular expression operators as well.
  395.  
  396.  
  397.  
  398.  
  399.  
  400.  
  401.  
  402.  
  403.  
  404.  
  405.  
  406.  
  407.  
  408.  
  409.  
  410.  
  411.  
  412.  
  413.  
  414.  
  415.  
  416.  
  417.  
  418.  
  419.  
  420.  
  421.  
  422.  
  423.  
  424.  
  425.  
  426.  
  427.  
  428.  
  429.  
  430.  
  431.  
  432.  
  433.                                                                 Page 7
  434.  
  435. PCCTS Advanced Tutorial 1.0x
  436.  
  437.  
  438. 2.4.  Complete ANTLR description (w/o symbol table management)
  439.  
  440.      The following code is the complete ANTLR description to recognize
  441. sc  programs.   Nothing  is  added  to  the symbol table and undefined
  442. variables/functions are not flagged.
  443.  
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450.  
  451.  
  452.  
  453.  
  454.  
  455.  
  456.  
  457.  
  458.  
  459.  
  460.  
  461.  
  462.  
  463.  
  464.  
  465.  
  466.  
  467.  
  468.  
  469.  
  470.  
  471.  
  472.  
  473.  
  474.  
  475.  
  476.  
  477.  
  478.  
  479.  
  480.  
  481.  
  482.  
  483.  
  484.  
  485.  
  486.  
  487.  
  488.  
  489.  
  490.  
  491.  
  492.  
  493.  
  494.  
  495.                                                                 Page 8
  496.  
  497. PCCTS Advanced Tutorial 1.0x
  498.  
  499.  
  500.  
  501. #header <<#include "charbuf.h">>
  502.  
  503. #token "[\t\ ]+"    << zzskip(); >>                /* Ignore White */
  504. #token "\n"         << zzline++; zzskip(); >>
  505. #token STRING "\"(~[\0-\0x1f\"\\]|(\\~[\0-\0x1f]))*\"" <<;>>
  506.  
  507. << main() { ANTLR(p(), stdin); } >>
  508.  
  509. p       :   ( func | "var" def ";" )*
  510.             "@"
  511.         ;
  512.  
  513. def     :   WORD
  514.         ;
  515.  
  516. func    :   WORD "\(" { def } "\)"
  517.             "\{"
  518.                 ( "var" def ";" )*
  519.                 ( statement )*
  520.             "\}"
  521.         ;
  522.  
  523. statement
  524.         :   expr ";"
  525.         |   "\{" ( statement )* "\}"
  526.         |   "if" "\(" expr "\)" statement {"else" statement}
  527.         |   "while" "\(" expr "\)" statement
  528.         |   "return" expr ";"
  529.         |   "print" expr ";"
  530.         ;
  531.  
  532. expr    :   WORD "=" expr
  533.         |   expr0
  534.         ;
  535.  
  536. expr0   :   expr1 ( ("==" | "!=") expr1 )*
  537.         ;
  538.  
  539. expr1   :   expr2 ( ("\+" | "\-") expr2 )*
  540.         ;
  541.  
  542. expr2   :   expr3 ( ( "\*" | "/" ) expr3 )*
  543.         ;
  544.  
  545. expr3   :   {"\-" } expr4
  546.         ;
  547.  
  548. expr4   :   STRING
  549.         |   WORD { "\(" { expr } "\)" }
  550.         |   "\(" expr "\)"
  551.         ;
  552.  
  553. #token WORD "[a-zA-Z]+"
  554.  
  555.  
  556.  
  557.                                                                 Page 9
  558.  
  559. PCCTS Advanced Tutorial 1.0x
  560.  
  561.  
  562. 2.5.  Makefile
  563.  
  564.      The following makefile can be used to  make  the  above  language
  565. description  into  an  executable  file.   We  assume  that  the ANTLR
  566. includes and standard attribute packages are located  in  a  directory
  567. accessible to us as tut1.g.
  568.  
  569.  
  570. #
  571. # Makefile for 1.00 tutorial (no symbol table stuff)
  572. # ANTLR creates parser.dlg, err.c, tut1.c, tokens.h
  573. # DLG creates scan.c, mode.h
  574. #
  575. CFLAGS= -I../h
  576. GRM=tut1
  577. SRC=scan.c $(GRM).c err.c
  578. OBJ=scan.o $(GRM).o err.o
  579.  
  580. tutorial: $(OBJ) $(SRC)
  581.     cc -o $(GRM) $(OBJ)
  582.  
  583. # build a parser and lexical description from a language description
  584. $(GRM).c parser.dlg : $(GRM).g
  585.     antlr -k 2 $(GRM).g
  586.  
  587. # build the scanner from a lexical description
  588. scan.c : parser.dlg
  589.     dlg -C2 parser.dlg scan.c
  590.  
  591.  
  592.  
  593. Remember that make wants a tab, not spaces, in  front  of  the  action
  594. statements (e.g. cc, antlr, ...).
  595.  
  596. 2.6.  Testing
  597.  
  598.      After successful completion of  make,  the  executable  tut  will
  599. exist  in  the current directory.  tut takes input from stdin.  There-
  600. fore, one parses a file via
  601.  
  602.  
  603. tut < file.sc
  604.  
  605.  
  606.  
  607. The prompt will return without a message  if  no  syntax  errors  were
  608. discovered.   However,  if  file contains lexical or syntactic errors,
  609. error messages will appear.  We have given no instructions related  to
  610. translation, so nothing happens if all is well.
  611.  
  612. 2.7.  Symbol table management
  613.  
  614.      The grammar presented thus far can only  recognize  sc  programs.
  615. No translation is possible because it does not deal with the semantics
  616.  
  617.  
  618.  
  619.                                                                Page 10
  620.  
  621. PCCTS Advanced Tutorial 1.0x
  622.  
  623.  
  624. of the input program only its structure.  To begin semantic  interpre-
  625. tation,  one  must  add  new  symbols  to a symbol table.  The symbols
  626. required to "understand" an sc program are
  627.  
  628. VAR       Symbol is a local (denoted with the #define constant LOCAL),
  629.           a parameter (PARAMETER) or global (GLOBAL) variable.
  630.  
  631. FUNC      Symbol is a function whose level is always GLOBAL.
  632.  
  633.      A symbol table record requires two fields: token which  indicates
  634. either  VAR or FUNC and level which is either LOCAL, PARAMETER or GLO-
  635. BAL.
  636.  
  637.      The PCCTS system comes with a simple symbol table  manager.   The
  638. source is documented well and its functions will be referenced without
  639. explanation here.  To use the functions, our grammar  must  include  a
  640. file  called  sym.h and define a symbol table structure.  We shall put
  641. the #include in the #header directive.
  642.  
  643.  
  644. #header <<#include "sym.h"
  645.                   #include "charbuf.h">>
  646.  
  647.  
  648.  
  649. The file sym.c contains the actual functions and must be  linked  into
  650. your  executable.   Our  makefile will handle this automatically.  The
  651. sym.c can be found in the support/sym  subdirectory  of  the  standard
  652. PCCTS installation; this should be copied into the tutorial directory.
  653.  
  654.      The symbol table manager requires a number of fields  within  the
  655. symbol  table  entry.   A template has been provided that the user can
  656. copy into their work directory and modify.  The template in sym.h will
  657. be  modified  in  our  case to include the two fields mentioned above-
  658. token and level.
  659.  
  660.  
  661. typedef struct symrec {
  662.                         char *symbol;
  663.                         struct symrec *next, *prev, **head, *scope;
  664.                         int token;  /* either FUNC or VAR */
  665.                         int level;  /* either LOCAL, GLOBAL, PARAMETER */
  666.             int offset; /* offset from sp on the stack */
  667.                         /* locals are - offset, param is 0 */
  668.                         /* used only in tut4; reserved */
  669.                 } Sym, *SymPtr;
  670.  
  671.  
  672.  
  673. We add the following definitions to the front of our grammar.
  674.  
  675.  
  676.  
  677.  
  678.  
  679.  
  680.  
  681.                                                                Page 11
  682.  
  683. PCCTS Advanced Tutorial 1.0x
  684.  
  685.  
  686.  
  687. <<
  688. #define HashTableSize       999
  689. #define StringTableSize     5000
  690. #define GLOBAL              0
  691. #define PARAMETER           1
  692. #define LOCAL               2
  693.  
  694. static Sym *globals = NULL;        /* global scope for symbols */
  695. >>
  696.  
  697.  
  698. where globals is used to track all global symbols (functions and vari-
  699. ables).  Also, to print out symbol scopes, we define a function called
  700. pScope(Sym *p) that dumps a scope to stdout.  It's  implementation  is
  701. unimportant  and given with the full grammar description listed below.
  702. To initialize the symbol table, we add a function call to  the  symbol
  703. table manager library yielding a new main().
  704.  
  705.  
  706. main()
  707. {
  708.     zzs_init(HashTableSize, StringTableSize);
  709.     ANTLR(p(), stdin);
  710. }
  711.  
  712.  
  713.  
  714.      When a variable, parameter or function is defined, we want to add
  715. that symbol to the symbol table.  We shall treat parameters like vari-
  716. ables grammatically and use field level to differentiate between them.
  717. When  a  WORD is found in rule def, we will add it to the symbol table
  718. using the scope and level passed into def.  The situation  is  compli-
  719. cated  slightly  by  the  fact that a local variable may have the same
  720. name as a global variable.  Scopes are linked lists that weave through
  721. the  symbol  table  grouping  all  entries within the same scope.  Our
  722. grammar for rule def becomes:
  723.  
  724.  
  725. def[Sym **scope, int level] : <<Sym *var;>> (WORD | VAR) ;
  726.  
  727.  
  728.  
  729. where the init-action defines a local variable called var.
  730.  
  731.      To handle the definition of previously unknown symbols, we add an
  732. action after the WORD reference.
  733.  
  734.  
  735.  
  736.  
  737.  
  738.  
  739.  
  740.  
  741.  
  742.  
  743.                                                                Page 12
  744.  
  745. PCCTS Advanced Tutorial 1.0x
  746.  
  747.  
  748.  
  749. ( WORD
  750.   <<zzs_scope($scope);         /* set current scope to scope passed in */
  751.     var = zzs_newadd($1.text); /* create entry, add text of WORD to table */
  752.     var->level = $level;       /* set the level to level passed in */
  753.     var->token = VAR;          /* symbol is a variable */
  754.   >>
  755. | VAR
  756. )
  757.  
  758.  
  759.  
  760. To deal with a symbol defined in another scope we  add  the  following
  761. action to the VAR reference.
  762.  
  763.  
  764. ( WORD
  765.   <<...>>
  766. | VAR
  767.   <<var = zzs_get($1.text);    /* get previous definition */
  768.     if ( level != var->level ) /* make sure we have a diff scope */
  769.     {
  770.       zzs_scope($scope);       /* same here as above for unknown */
  771.       var = zzs_newadd($1.text);
  772.       var->level = $level;
  773.       var->token = VAR;
  774.     }
  775.     else printf("redefined variable ignored: %s\n", $1.text);
  776.   >>
  777. )
  778.  
  779.  
  780.  
  781. Note that this implies that the lexical analyzer will modify the token
  782. number according to its definition in the symbol table (if any).  This
  783. is generally not a good idea, but can be quite helpful when trying  to
  784. remove  nasty  ambiguities  in  your grammar.  Typically more than one
  785. token of lookahead makes it unnecessary to use "derived"  tokens.   We
  786. do  so  here  to  illustrate  the  interaction of lexical analyzer and
  787. parser.
  788.  
  789.      Rule p must be modified to pass a scope and level  to  rule  def.
  790. In addition, we will remove the global scope at the end of parsing and
  791. print out the symbols.
  792.  
  793.  
  794. p       :   <<Sym *p;>>
  795.             ( func | "var" def[&globals, GLOBAL] ";" )*
  796.             <<p = zzs_rmscope(&globals);
  797.               printf("Globals:\n");
  798.               if ( p != NULL ) pScope(p);
  799.             >>
  800.             "@"
  801.         ;
  802.  
  803.  
  804.  
  805.                                                                Page 13
  806.  
  807. PCCTS Advanced Tutorial 1.0x
  808.  
  809.  
  810.      Rule func now must create a FUNC symbol table entry and define  a
  811. VAR  entry  for  its  parameter  if  one exists.  Rule func checks for
  812. duplicate FUNC entries by only matching unknown WORD's.  If a function
  813. had been previously defined, its token would be FUNC.
  814.  
  815.  
  816. func    :   <<Sym *locals=NULL, *var, *p;>>
  817.             WORD
  818.                         <<zzs_scope(&globals);
  819.                           var = zzs_newadd($1.text);
  820.                       var->level = GLOBAL;
  821.                           var->token = FUNC;
  822.                         >>
  823.             "\(" { def[&locals, PARAMETER] } "\)"
  824.             "\{"
  825.                  ( "var" def[&locals, LOCAL] ";" )*
  826.                  ( statement )*
  827.             "\}"
  828.             <<p = zzs_rmscope(&locals);
  829.               printf("Locals for %s:\n", $1.text);
  830.               if ( p != NULL ) pScope(p);
  831.             >>
  832.         ;
  833.  
  834.  
  835.  
  836. At the end of the function, we remove the  local  scope  of  variables
  837. (and parameter if it exists) and print the symbols out to stdout.
  838.  
  839.      When a WORD is encountered on the input stream, we need  to  look
  840. it up in the symbol table to find out whether it is a variable (param-
  841. eter) or a function.  The token number needs to be changed accordingly
  842. before  the  parser  sees  it so that it will not try to match a WORD.
  843. Any WORD references in an expression that are not defined in the  sym-
  844. bol  table are undefined variables.  We accomplish this token "deriva-
  845. tion" strategy by attaching an action to the  regular  expression  for
  846. WORD.
  847.  
  848.  
  849. #token WORD "[a-zA-Z]+"
  850.         <<{
  851.                 Sym *p = zzs_get(LATEXT(1));
  852.                 if ( p != NULL ) NLA = p->token;
  853.         }>>
  854.  
  855.  
  856.  
  857. The macro LATEXT(1) is always set to the text  matched  on  the  input
  858. stream  for  the  current token.  NLA is the next token of look-ahead.
  859. We need to change this from WORD to whatever is found  in  the  symbol
  860. table.
  861.  
  862.      Rules for statements and expressions do not  change  when  adding
  863. symbol  table  management  because  they  simply  apply a structure to
  864.  
  865.  
  866.  
  867.                                                                Page 14
  868.  
  869. PCCTS Advanced Tutorial 1.0x
  870.  
  871.  
  872. grammar symbols and do not introduce new ones.
  873.  
  874. 2.8.  Complete ANTLR description (with symbol table management)
  875.  
  876.      The following code is the complete ANTLR description to recognize
  877. sc  programs.   Functions,  variables  and parameters are added to the
  878. symbol table and are printed to stdout after function definitions  and
  879. at the end of the sc program.
  880.  
  881.  
  882. #header <<
  883.     #include "sym.h"
  884.     #include "charbuf.h"
  885. >>
  886.  
  887. #token "[\t\ ]+"    << zzskip(); >>                /* Ignore White */
  888. #token "\n"         << zzline++; zzskip(); >>
  889. #token STRING "\"(~[\0-\0x1f\"\\]|(\\~[\0-\0x1f]))*\"" <<;>>
  890.  
  891. <<
  892. #define HashTableSize       999
  893. #define StringTableSize     5000
  894. #define GLOBAL              0
  895. #define PARAMETER           1
  896. #define LOCAL               2
  897.  
  898. static Sym *globals = NULL; /* global scope for symbols */
  899.  
  900.  
  901.  
  902.  
  903. main()
  904. {
  905.     zzs_init(HashTableSize, StringTableSize);
  906.     ANTLR(p(), stdin);
  907. }
  908.  
  909. pScope(p)
  910. Sym *p;
  911. {
  912.     for (; p!=NULL; p=p->scope)
  913.     {
  914.         printf("\tlevel %d | %-12s | %-15s\n",
  915.             p->level,
  916.             zztokens[p->token],
  917.             p->symbol);
  918.     }
  919. }
  920. >>
  921.  
  922.  
  923.  
  924.  
  925.  
  926.  
  927.  
  928.  
  929.                                                                Page 15
  930.  
  931. PCCTS Advanced Tutorial 1.0x
  932.  
  933.  
  934.  
  935. p       :   <<Sym *p;>>
  936.             ( func | "var" def[&globals, GLOBAL] ";" )*
  937.             <<p = zzs_rmscope(&globals);
  938.               printf("Globals:\n");
  939.               pScope(p);
  940.             >>
  941.             "@"
  942.         ;
  943.  
  944. def[Sym **scope, int level]
  945.         :   <<Sym *var;>>
  946.             (   WORD
  947.                 <<zzs_scope($scope);
  948.                   var = zzs_newadd($1.text);
  949.                   var->level = $level;
  950.                   var->token = VAR;
  951.                 >>
  952.             |   VAR
  953.                 <<var = zzs_get($1.text);
  954.                   if ( $level != var->level )
  955.                   {
  956.                     zzs_scope($scope);
  957.                     var = zzs_newadd($1.text);
  958.                     var->level = $level;
  959.                     var->token = VAR;
  960.                   }
  961.                   else printf("redefined variable ignored: %s\n", $1.text);
  962.                 >>
  963.             )
  964.         ;
  965.  
  966.  
  967.  
  968.  
  969.  
  970.  
  971.  
  972.  
  973.  
  974.  
  975.  
  976.  
  977.  
  978.  
  979.  
  980.  
  981.  
  982.  
  983.  
  984.  
  985.  
  986.  
  987.  
  988.  
  989.  
  990.  
  991.                                                                Page 16
  992.  
  993. PCCTS Advanced Tutorial 1.0x
  994.  
  995.  
  996.  
  997. func    :   <<Sym *locals=NULL, *var, *p;>>
  998.             WORD
  999.             <<zzs_scope(&globals);
  1000.               var = zzs_newadd($1.text);
  1001.               var->level = GLOBAL;
  1002.               var->token = FUNC;
  1003.             >>
  1004.             "\(" { def[&locals, PARAMETER] } "\)"
  1005.             "\{"
  1006.                 ( "var" def[&locals, LOCAL] ";" )*
  1007.                 ( statement )*
  1008.             "\}"
  1009.             <<p = zzs_rmscope(&locals);
  1010.               printf("Locals for %s:\n", $1.text);
  1011.               pScope(p);
  1012.             >>
  1013.         ;
  1014.  
  1015. statement
  1016.         :   expr ";"
  1017.         |   "\{" ( statement )* "\}"
  1018.         |   "if" "\(" expr "\)" statement
  1019.             {"else" statement}
  1020.         |   "while" "\(" expr "\)" statement
  1021.         |   "return" expr ";"
  1022.         |   "print" expr ";"
  1023.         ;
  1024.  
  1025.  
  1026.  
  1027.  
  1028.  
  1029.  
  1030.  
  1031.  
  1032.  
  1033.  
  1034.  
  1035.  
  1036.  
  1037.  
  1038.  
  1039.  
  1040.  
  1041.  
  1042.  
  1043.  
  1044.  
  1045.  
  1046.  
  1047.  
  1048.  
  1049.  
  1050.  
  1051.  
  1052.  
  1053.                                                                Page 17
  1054.  
  1055. PCCTS Advanced Tutorial 1.0x
  1056.  
  1057.  
  1058.  
  1059. expr    :   VAR "=" expr
  1060.         |   expr0
  1061.         ;
  1062.  
  1063. expr0   :   expr1 ( (   "=="
  1064.                     |   "!="
  1065.                     )
  1066.                     expr1
  1067.                   )*
  1068.         ;
  1069.  
  1070. expr1   :   expr2 ( (   "\+"
  1071.                     |   "\-"
  1072.                     )
  1073.                     expr2
  1074.                   )*
  1075.         ;
  1076.  
  1077. expr2   :   expr3 ( (   "\*"
  1078.                     |   "/"
  1079.                     )
  1080.                     expr3
  1081.                   )*
  1082.         ;
  1083.  
  1084. expr3   :   {"\-" } expr4
  1085.         ;
  1086.  
  1087.  
  1088.  
  1089.  
  1090. expr4   :   STRING
  1091.         |   VAR
  1092.         |   (   FUNC
  1093.             |   WORD
  1094.             )
  1095.             "\(" { expr } "\)"
  1096.         |   "\(" expr "\)"
  1097.     ;
  1098.  
  1099. #token WORD "[a-zA-Z]+"
  1100.     <<{
  1101.         Sym *p = zzs_get(LATEXT(1));
  1102.         if ( p != NULL ) NLA = p->token;
  1103.     }>>
  1104.  
  1105.  
  1106.  
  1107. 2.9.  File sym.h
  1108.  
  1109.      The following is a modification of the  sym.h  template  provided
  1110. with  PCCTS.  The fields of the symbol table entry structure have aug-
  1111. mented for our purposes as outlined above.
  1112.  
  1113.  
  1114.  
  1115.                                                                Page 18
  1116.  
  1117. PCCTS Advanced Tutorial 1.0x
  1118.  
  1119.  
  1120.  
  1121. /* define some hash function */
  1122. #ifndef HASH
  1123. #define HASH(p, h) while ( *p != '\0' ) h = (h<<1) + *p++;
  1124. #endif
  1125.  
  1126. typedef struct symrec {
  1127.             char * symbol;
  1128.             struct symrec *next, *prev, **head, *scope;
  1129.             unsigned hash;
  1130.             int token;  /* either FUNC or VAR */
  1131.             int level;  /* either LOCAL, GLOBAL, PARAMETER */
  1132.             int offset; /* offset from sp on the stack */
  1133.                         /* locals are - offset, param is 0 */
  1134.                         /* used only tut4; reserved */
  1135.         } Sym, *SymPtr;
  1136.  
  1137. void zzs_init();
  1138. void zzs_done();
  1139. void zzs_add();
  1140. Sym *zzs_get();
  1141. void zzs_del();
  1142. void zzs_keydel();
  1143. Sym **zzs_scope();
  1144. Sym *zzs_rmscope();
  1145. void zzs_stat();
  1146. Sym *zzs_new();
  1147. Sym *zzs_newadd();
  1148. char *zzs_strdup();
  1149.  
  1150.  
  1151.  
  1152. 2.10.  Makefile (for use with symbol table management)
  1153.  
  1154.      The following makefile can be used to  make  the  above  language
  1155. description  into  an  executable  file.   We  assume  that  the ANTLR
  1156. includes and standard attribute packages are located  in  a  directory
  1157. accessible  to  us  as  current working directory.  The grammar listed
  1158. above must be in file tut2.g.
  1159.  
  1160.  
  1161.  
  1162.  
  1163.  
  1164.  
  1165.  
  1166.  
  1167.  
  1168.  
  1169.  
  1170.  
  1171.  
  1172.  
  1173.  
  1174.  
  1175.  
  1176.  
  1177.                                                                Page 19
  1178.  
  1179. PCCTS Advanced Tutorial 1.0x
  1180.  
  1181.  
  1182.  
  1183. #
  1184. # Makefile for 1.00 tutorial
  1185. # ANTLR creates parser.dlg, err.c, tut1.c
  1186. # DLG creates scan.c
  1187. #
  1188. CFLAGS= -I../h
  1189. GRM=tut2
  1190. SRC=scan.c $(GRM).c err.c sym.c
  1191. OBJ=scan.o $(GRM).o err.o sym.o
  1192.  
  1193. tutorial: $(OBJ) $(SRC)
  1194.     cc -o $(GRM) $(OBJ)
  1195.  
  1196. $(GRM).c parser.dlg : $(GRM).g
  1197.     antlr -k 2 $(GRM).g
  1198.  
  1199. scan.c : parser.dlg
  1200.     dlg -C2 parser.dlg scan.c
  1201.  
  1202.  
  1203.  
  1204. 2.11.  Sample input/output
  1205.  
  1206.      The current state of the program accepts input like the following
  1207. sample.
  1208.  
  1209.  
  1210. var i;
  1211. var j;
  1212.  
  1213. f(k)
  1214. {
  1215.     var local;
  1216.     var j;
  1217.  
  1218.     if ( "true" ) local = "zippo";
  1219. }
  1220.  
  1221. g()
  1222. {
  1223.     var note;
  1224.  
  1225.     note = "1";
  1226.     while ( note )
  1227.     {
  1228.         i = "456";
  1229.     }
  1230. }
  1231.  
  1232.  
  1233.  
  1234. The output of our executable, tut, would be
  1235.  
  1236.  
  1237.  
  1238.  
  1239.                                                                Page 20
  1240.  
  1241. PCCTS Advanced Tutorial 1.0x
  1242.  
  1243.  
  1244.  
  1245. Locals for f:
  1246.         level 2 | VAR          | j
  1247.         level 2 | VAR          | local
  1248.         level 1 | VAR          | k
  1249. Locals for g:
  1250.         level 2 | VAR          | note
  1251. Globals:
  1252.         level 0 | FUNC         | g
  1253.         level 0 | FUNC         | f
  1254.         level 0 | VAR          | j
  1255.         level 0 | VAR          | i
  1256.  
  1257.  
  1258.  
  1259. Note that the parameter k is level 1 for PARAMETER and the local vari-
  1260. able local is level 2 for LOCAL.
  1261.  
  1262. 3.  Translate sc to stack code
  1263.  
  1264.      Generating code for a stack machine is simple and can be done  by
  1265. simply  adding  printf()  actions  to  the  grammar in the appropriate
  1266. places.
  1267.  
  1268.      We begin with a discussion of the stack machine and how  to  gen-
  1269. erate  code  for it.  Next we augment our grammar with actions to dump
  1270. stack code to stdout.
  1271.  
  1272. 3.1.  A simple stack machine for sc
  1273.  
  1274.      Our stack machine consists of a single CPU,  a  finite  stack  of
  1275. strings,  a  finite  memory,  a stack pointer (sp) and a frame pointer
  1276. (fp).  All data items used by stack programs  are  strings  (currently
  1277. set  to  a  maximum  length of 100).  Our string stack grows downwards
  1278. towards 0 from the maximum stack height.
  1279.  
  1280.      To make implementation simple, our stack code will actually be  a
  1281. sequence  of  macro  invocations in a C program.  This way C will take
  1282. care of control-flow and allocating space etc...   The  minimum  stack
  1283. code  program  defines a _main and includes sc.h which contains all of
  1284. the stack code macros:
  1285.  
  1286.  
  1287. #include "sc.h"
  1288. _main()
  1289. {
  1290.     BEGIN;
  1291.     END;
  1292. }
  1293.  
  1294.  
  1295.  
  1296. The BEGIN and END macros are explained below.
  1297.  
  1298.  
  1299.  
  1300.  
  1301.                                                                Page 21
  1302.  
  1303. PCCTS Advanced Tutorial 1.0x
  1304.  
  1305.  
  1306. 3.1.1.  Functions
  1307.  
  1308.      Every sc program requires a main which will we translate to _main
  1309. (a  C  function main will call _main).  Other functions are translated
  1310. verbatim.  The parameter to your main program will be the  first  com-
  1311. mand line argument when you execute your sc program (after translation
  1312. to C).  If no command line argument is specified, a "" is pushed.
  1313.  
  1314.      Parameters are pushed on the string stack before  a  function  is
  1315. called,  so no argument is needed to the resulting C function.  Return
  1316. values are implicitly strings but are  also  returned  on  the  string
  1317. stack -  avoiding  the need to define a return type of the C function.
  1318. An "instruction" (macro) called BEGIN is executed before any other  in
  1319. a  function.   This  saves the current frame pointer and then makes it
  1320. point to the argument passed  into  the  function.   END  is  used  to
  1321. restore  the  frame  pointer  to its previous value and make the stack
  1322. pointer point to the return value.  After a function call, the top  of
  1323. stack is always the return value.
  1324.  
  1325.      Arguments and  local  variables  are  at  offsets  to  the  frame
  1326. pointer.  The optional argument is at offset 0.  The first local vari-
  1327. able is at offset 1, the second at offset 2 and so on.  Graphically,
  1328.  
  1329.  
  1330.        |    .      |
  1331.        |    .      |
  1332.        |   arg     |   fp + 0
  1333.        | 1st local |   fp - 1
  1334.        | 2nd local |   fp - 2
  1335.        |   ...     |
  1336.        |    .      |
  1337.        |    .      |
  1338.  
  1339.  
  1340.  
  1341. A dummy argument is pushed by the calling function if no  argument  is
  1342. specified.
  1343.  
  1344.      To translate a function,
  1345.  
  1346.  
  1347. f(arg)
  1348. {
  1349. }
  1350.  
  1351.  
  1352.  
  1353. we simply dump the following
  1354.  
  1355.  
  1356.  
  1357.  
  1358.  
  1359.  
  1360.  
  1361.  
  1362.  
  1363.                                                                Page 22
  1364.  
  1365. PCCTS Advanced Tutorial 1.0x
  1366.  
  1367.  
  1368.  
  1369. f()
  1370. {
  1371.     BEGIN;
  1372.     END;
  1373. }
  1374.  
  1375.  
  1376.  
  1377. Note that the argument disappears because we  pass  arguments  on  the
  1378. string stack not the C hardware stack.
  1379.  
  1380. 3.1.2.  Variables
  1381.  
  1382.      Global variables of the form
  1383.  
  1384.  
  1385. var name;
  1386.  
  1387.  
  1388.  
  1389. are translated to
  1390.  
  1391.  
  1392. SCVAR name;
  1393.  
  1394.  
  1395.  
  1396. where SCVAR is a C type defined in sc.h that  makes  space  for  a  sc
  1397. variable.
  1398.  
  1399.      Local variables are allocated on the string stack and are created
  1400. at  run time via the instruction LOCAL.  Each execution of LOCAL allo-
  1401. cates space for one more local variable on the stack.  LOCAL's must be
  1402. executed  after the BEGIN but before any other stack code instruction.
  1403. The END macro resets the stack pointer so that these locals  disappear
  1404. after each function invocation.  For example,
  1405.  
  1406.  
  1407. main()
  1408. {
  1409.         var i;
  1410.         var j;
  1411. }
  1412.  
  1413.  
  1414.  
  1415. is translated to:
  1416.  
  1417.  
  1418.  
  1419.  
  1420.  
  1421.  
  1422.  
  1423.  
  1424.  
  1425.                                                                Page 23
  1426.  
  1427. PCCTS Advanced Tutorial 1.0x
  1428.  
  1429.  
  1430.  
  1431. #include "sc.h"
  1432. _main()
  1433. {
  1434.     BEGIN;
  1435.     LOCAL;
  1436.     LOCAL;
  1437.     END;
  1438. }
  1439.  
  1440.  
  1441.  
  1442. 3.1.3.  Expressions
  1443.  
  1444.      Operator precedence is defined implicitly in top-down (LL)  gram-
  1445. mars.   The  deeper the level of recursion, the higher the precedence.
  1446. To generate code for operators, one prints out the correct  macro  for
  1447. that  operator  after the two operators have been seen (because we are
  1448. generating code for a stack machine).  If  the  operator  is  a  unary
  1449. operator like negate, we wait until the operand is seen and then print
  1450. the operator.  For instance, expr1,
  1451.  
  1452.  
  1453. expr1   :   expr2 ( ("\+"|"\-") expr2)*
  1454.         ;
  1455.  
  1456.  
  1457.  
  1458. would be translated as:
  1459.  
  1460.  
  1461. expr1   :   <<char *op;>>
  1462.             expr2 ( (   "\+" <<op="ADD";>>
  1463.                     |   "\-" <<op="SUB";>>
  1464.                     )
  1465.                     expr2
  1466.                     <<printf("\t%s;\n", op);>>
  1467.                   )*
  1468.         ;
  1469.  
  1470.  
  1471.  
  1472.  
  1473. where ADD and SUB are sc stack machine macros defined below.
  1474.  
  1475.      The assignment operator groups right to left  and  must  generate
  1476. code that duplicates itself after each assignment so that the value of
  1477. the expression is on the stack for any chained assignement.  For exam-
  1478. ple,
  1479.  
  1480.  
  1481.  
  1482.  
  1483.  
  1484.  
  1485.  
  1486.  
  1487.                                                                Page 24
  1488.  
  1489. PCCTS Advanced Tutorial 1.0x
  1490.  
  1491.  
  1492.  
  1493. main()
  1494. {
  1495.     var a;
  1496.     var b;
  1497.  
  1498.     a = b = "test";
  1499. }
  1500.  
  1501.  
  1502.  
  1503. would be translated to:
  1504.  
  1505.  
  1506. #include "sc.h"
  1507. _main()             /* main() */
  1508. {
  1509.     BEGIN;
  1510.     LOCAL;          /* var a; */
  1511.     LOCAL;          /* var b; */
  1512.     SPUSH("test");  /* a = b = "test"; */
  1513.     DUP;
  1514.     LSTORE(2);      /* store into b */
  1515.     DUP;
  1516.     LSTORE(1);      /* store into a */
  1517.     POP;
  1518.     END;
  1519. }
  1520.  
  1521.  
  1522.  
  1523.      Since an expression is a statement, it is possible that  a  value
  1524. could be left on the stack.  For example,
  1525.  
  1526.  
  1527. main()
  1528. {
  1529.         "expression";
  1530. }
  1531.  
  1532.  
  1533.  
  1534. We must pop this extraneous value off the stack:
  1535.  
  1536.  
  1537. #include "sc.h"
  1538. _main()
  1539. {
  1540.     BEGIN;
  1541.     SPUSH("expression");
  1542.     POP;
  1543.     END;
  1544. }
  1545.  
  1546.  
  1547.  
  1548.  
  1549.                                                                Page 25
  1550.  
  1551. PCCTS Advanced Tutorial 1.0x
  1552.  
  1553.  
  1554. 3.1.4.  Instructions
  1555.  
  1556.      All instructions take operands from the stack and return  results
  1557. on  the stack.  Some have no side effects on the stack but alter the C
  1558. program counter.
  1559.  
  1560. PUSH(v)     Push the value of variable v onto the stack.
  1561.  
  1562. SPUSH(s)    Push the value of the string constant s onto the stack.
  1563.  
  1564. LPUSH(n)    Push the value of the local variable or function  argument
  1565.             at offset n onto the stack.
  1566.  
  1567. STORE(v)    Pop the top of stack and store it into variable v.
  1568.  
  1569. LSTORE(n)   Pop the top of stack and store it into local  variable  or
  1570.             function argument at offset n.
  1571.  
  1572. POP         Pop the top of stack; stack is  one  string  smaller.   No
  1573.             side effects with data memory.
  1574.  
  1575. LOCAL       Create space on the stack  for  a  local  variable.   Must
  1576.             appear  after  BEGIN but before any other instruction in a
  1577.             function.
  1578.  
  1579. BRF(a)      Branch, if top of stack is "false" or "0", to "address"  a
  1580.             (C label); top of stack is popped off.
  1581.  
  1582. BRT(a)      Branch, if top of stack is "true" or "1", to  "address"  a
  1583.             (C label); top of stack is popped off.
  1584.  
  1585. BR(a)       Branch to "address" a (C label).  Stack is not touched.
  1586.  
  1587. CALL(f)     Call the function f.  Returns with result on stack top.
  1588.  
  1589. PRINT       Pop the top of stack and print the string to stdout.
  1590.  
  1591. RETURN      Set the return value to the top of stack.  Return from the
  1592.             function.
  1593.  
  1594. EQ          Perform stack[sp] = (stack[sp+1] == stack[sp]).
  1595.  
  1596. NEQ         Perform stack[sp] = (stack[sp+1] != stack[sp]).
  1597.  
  1598. ADD         Perform stack[sp] = (stack[sp+1] + stack[sp]).
  1599.  
  1600. SUB         Perform stack[sp] = (stack[sp+1] - stack[sp]).
  1601.  
  1602. MUL         Perform stack[sp] = (stack[sp+1] * stack[sp]).
  1603.  
  1604. DIV         Perform stack[sp] = (stack[sp+1] / stack[sp]).
  1605.  
  1606. NEG         Perform stack[sp] = -stack[sp].
  1607.  
  1608.  
  1609.  
  1610.  
  1611.                                                                Page 26
  1612.  
  1613. PCCTS Advanced Tutorial 1.0x
  1614.  
  1615.  
  1616. DUP         Perform PUSH(stack[sp]).
  1617.  
  1618. BEGIN       Function preamble.
  1619.  
  1620. END         Function cleanup.
  1621.  
  1622.      Boolean operations yield string constants "false" for  false  and
  1623. true for true.  All other operations yield string constants represent-
  1624. ing numerical values ("3"+"4" is "7").
  1625.  
  1626. 3.2.  Examples
  1627.  
  1628.      The sample factorial program from above,
  1629.  
  1630.  
  1631. main(n)
  1632. {
  1633.         print fact(n);
  1634.         print "\n";
  1635. }
  1636.  
  1637. fact(n)
  1638. {
  1639.         if ( n == "0" ) return "1";
  1640.         return n * fact(n - "1");
  1641. }
  1642.  
  1643.  
  1644.  
  1645. would be translated to:
  1646.  
  1647.  
  1648. #include "sc.h"
  1649. _main()             /* main(n) */
  1650. {                   /* { */
  1651.     BEGIN;
  1652.     LPUSH(0);       /* print fact(n); */
  1653.     CALL(fact);
  1654.     PRINT;
  1655.     SPUSH("\n");    /* print "\n"; */
  1656.     PRINT;
  1657.     END;            /* } */
  1658. }
  1659.  
  1660.  
  1661.  
  1662.  
  1663.  
  1664.  
  1665.  
  1666.  
  1667.  
  1668.  
  1669.  
  1670.  
  1671.  
  1672.  
  1673.                                                                Page 27
  1674.  
  1675. PCCTS Advanced Tutorial 1.0x
  1676.  
  1677.  
  1678.  
  1679. fact()              /* fact(n) */
  1680. {
  1681.     BEGIN;
  1682.     LPUSH(0);       /* if ( n == "0" ) */
  1683.     SPUSH("0");
  1684.     EQ;
  1685.     BRF(iflabel0);
  1686.     SPUSH("1");     /* return "1"; */
  1687.     RETURN;
  1688. iflabel0: ;
  1689.     LPUSH(0);       /* return n * fact(n - "1"); */
  1690.     LPUSH(0);
  1691.     SPUSH("1");
  1692.     SUB;
  1693.     CALL(fact);
  1694.     MUL;
  1695.     RETURN;
  1696.     END;            /* } */
  1697. }
  1698.  
  1699.  
  1700.  
  1701.  
  1702. 3.3.  Augmenting grammar to dump stack code
  1703.  
  1704.      In order to generate code, we must  track  the  offset  of  local
  1705. variables.   To  do  so,  we  add a field, offset, to our symbol table
  1706. record:
  1707.  
  1708.  
  1709. typedef struct symrec {
  1710.     char * symbol;
  1711.     struct symrec *next, *prev, **head, *scope;
  1712.     unsigned hash;
  1713.     int token;  /* either FUNC or VAR */
  1714.     int level;  /* either LOCAL, GLOBAL, PARAMETER */
  1715.     int offset; /* offset from sp on the stack */
  1716.                 /* locals are negative offsets, param is 0 */
  1717.     } Sym, *SymPtr;
  1718.  
  1719.  
  1720.  
  1721.      We begin modifying our grammar by making a global  variable  that
  1722. tracks  the offset of local variables and defining a variable to track
  1723. label numbers:
  1724.  
  1725.  
  1726. static int current_local_var_offset, LabelNum=0;
  1727.  
  1728.  
  1729.  
  1730.      Because the translation of all programs must include the sc stack
  1731. machine definitions, we add a printf to rule p:
  1732.  
  1733.  
  1734.  
  1735.                                                                Page 28
  1736.  
  1737. PCCTS Advanced Tutorial 1.0x
  1738.  
  1739.  
  1740.  
  1741. p       :   <<Sym *p; printf("#include \"sc.h\"\n"); >>
  1742.             ( func | "var" def[&globals, GLOBAL] ";" )*
  1743.             <<  p = zzs_rmscope(&globals); >>
  1744.             "@"
  1745.         ;
  1746.  
  1747.  
  1748.  
  1749.      In order to generate the variable definition  macros  and  update
  1750. the symbol table, we modify rule def as follows:
  1751.  
  1752.  
  1753. def[Sym **scope, int level]
  1754.         :   <<Sym *var;>>
  1755.             (   WORD
  1756.                 <<zzs_scope($scope);
  1757.                   var = zzs_newadd($1.text);
  1758.                   var->level = $level;
  1759.                   var->token = VAR;
  1760.                   var->offset = current_local_var_offset++;
  1761.                   switch(var->level) {
  1762.                         case GLOBAL: printf("SCVAR %s;\n", $1.text); break;
  1763.                         case  LOCAL : printf("\tLOCAL;\n"); break;
  1764.                   }
  1765.                 >>
  1766.             |   VAR
  1767.                 <<var = zzs_get($1.text);
  1768.                   if ( $level != var->level )
  1769.                   {
  1770.                     zzs_scope($scope);
  1771.                     var = zzs_newadd($1.text);
  1772.                     var->level = $level;
  1773.                     var->token = VAR;
  1774.                     var->offset = current_local_var_offset++;
  1775.  
  1776.                     switch(var-> level) {
  1777.                         case GLOBAL: printf("\tSCVAR %s;\n",$1.text);break;
  1778.                         case  LOCAL : printf("\tLOCAL;\n"); break;
  1779.                     }
  1780.                   }
  1781.                   else printf("redefined variable ignored: %s\n",$1.text);
  1782.                 >>
  1783.             )
  1784.         ;
  1785.  
  1786.  
  1787.  
  1788.      The function definition rule must now dump a function template to
  1789. stdout  and  generate the BEGIN and END macros.  func must also update
  1790. current_local_var_offset.  Note that the code to dump symbols is gone.
  1791.  
  1792.  
  1793.  
  1794.  
  1795.  
  1796.  
  1797.                                                                Page 29
  1798.  
  1799. PCCTS Advanced Tutorial 1.0x
  1800.  
  1801.  
  1802.  
  1803. func :  <<Sym *locals=NULL, *var, *p; current_local_var_offset =0;>>
  1804.             WORD
  1805.             <<zzs_scope(&globals);
  1806.               var = zzs_newadd($1.text);
  1807.               var->level = GLOBAL;
  1808.               var->token = FUNC;
  1809.  
  1810.               if (strcmp("main",$1.text)) { printf("%s()\n",$1.text); }
  1811.               else printf("_main()\n");
  1812.             >>
  1813.             "\(" (  def[&locals, PARAMETER]
  1814.                  |  <<current_local_var_offset = 1;>>
  1815.                  )
  1816.             "\)"
  1817.             "\{" << printf("{\n\tBEGIN;\n"); >>
  1818.                 ( "var" def[&locals, LOCAL] ";" )*
  1819.                 ( statement )*
  1820.             "\}" << printf("\tEND;\n}\n"); >>
  1821.             <<  p = zzs_rmscope(&locals); >>
  1822.         ;
  1823.  
  1824.  
  1825.  
  1826.      Statements are easy to handle since expr generates  most  of  the
  1827. code.
  1828.  
  1829.  
  1830. statement : <<int n;>>
  1831.             expr ";"            <<printf("\tPOP;\n");>>
  1832.         |   "\{" ( statement )* "\}"
  1833.         |   "if" "\(" expr "\)" << n = LabelNum++;
  1834.                                    printf("\tBRF(iflabel%d);\n",n); >>
  1835.                 statement       << printf("iflabel%d: ;\n",n); >>
  1836.             {"else" statement}
  1837.         |
  1838.             "while"             << n = LabelNum++;
  1839.                                    printf("wbegin%d: ;\n", n); >>
  1840.             "\(" expr "\)"      << printf("\tBRF(wend%d);\n",n); >>
  1841.             statement           << printf("\tBR(wbegin%d);\n", n); >>
  1842.                                 << printf("wend%d: ;\n",n); >>
  1843.                                 << n++; >>
  1844.         |   "return" expr ";"   << printf("\tRETURN;\n"); >>
  1845.         |   "print" expr ";"    << printf("\tPRINT;\n"); >>
  1846.         ;
  1847.  
  1848.  
  1849.  
  1850. 3.4.  Full translator
  1851.  
  1852.      The following grammar accepts programs in sc and translates  them
  1853. into stack code.
  1854.  
  1855.  
  1856.  
  1857.  
  1858.  
  1859.                                                                Page 30
  1860.  
  1861. PCCTS Advanced Tutorial 1.0x
  1862.  
  1863.  
  1864.  
  1865. #header <<#include "sym.h"
  1866.           #include "charbuf.h"
  1867.         >>
  1868.  
  1869. #token "[\t\ ]+"  << zzskip(); >>                /* Ignore White */
  1870. #token "\n"       << zzline++; zzskip(); >>
  1871. #token STRING     "\"(~[\0-\0x1f\"\\]|(\\~[\0-\0x1f]))*\"" <<;>>
  1872.  
  1873. <<
  1874. #define HashTableSize       999
  1875. #define StringTableSize     5000
  1876. #define GLOBAL              0
  1877. #define PARAMETER           1
  1878. #define LOCAL               2
  1879.  
  1880. static Sym *globals = NULL; /* global scope for symbols */
  1881. static int current_local_var_offset, LabelNum=0;
  1882.  
  1883.  
  1884.  
  1885.  
  1886. main()
  1887. {
  1888.     zzs_init(HashTableSize, StringTableSize);
  1889.     ANTLR(p(), stdin);
  1890. }
  1891.  
  1892. pScope(p)
  1893. Sym *p;
  1894. {
  1895.     for (; p!=NULL; p=p->scope)
  1896.     {
  1897.         printf("\tlevel %d | %-12s | %-15s\n",
  1898.             p->level,
  1899.             zztokens[p->token],
  1900.             p->symbol);
  1901.     }
  1902. }
  1903. >>
  1904.  
  1905.  
  1906.  
  1907.  
  1908.  
  1909.  
  1910.  
  1911.  
  1912.  
  1913.  
  1914.  
  1915.  
  1916.  
  1917.  
  1918.  
  1919.  
  1920.  
  1921.                                                                Page 31
  1922.  
  1923. PCCTS Advanced Tutorial 1.0x
  1924.  
  1925.  
  1926.  
  1927. p       :   <<Sym *p; printf("#include \"sc.h\"\n"); >>
  1928.             ( func | "var" def[&globals, GLOBAL] ";" )*
  1929.             <<  p = zzs_rmscope(&globals); >>
  1930.             "@"
  1931.         ;
  1932.  
  1933. def[Sym **scope, int level]
  1934.         :   <<Sym *var;>>
  1935.             (   WORD
  1936.                 <<zzs_scope($scope);
  1937.                   var = zzs_newadd($1.text);
  1938.                   var->level = $level;
  1939.                   var->token = VAR;
  1940.                   var->offset = current_local_var_offset++;
  1941.                   switch(var->level) {
  1942.                         case  GLOBAL: printf("SCVAR %s;\n", $1.text); break;
  1943.                         case  LOCAL : printf("\tLOCAL;\n"); break;
  1944.                   }
  1945.                 >>
  1946.             |   VAR
  1947.                 <<var = zzs_get($1.text);
  1948.                   if ( $level != var->level )
  1949.                   {
  1950.                     zzs_scope($scope);
  1951.                     var = zzs_newadd($1.text);
  1952.                     var->level = $level;
  1953.                     var->token = VAR;
  1954.                     var->offset = current_local_var_offset++;
  1955.  
  1956.                     switch(var-> level) {
  1957.                         case  GLOBAL: printf("\tSCVAR %s;\n", $1.text); break;
  1958.                         case  LOCAL : printf("\tLOCAL;\n"); break;
  1959.                     }
  1960.                   }
  1961.                   else printf("redefined variable ignored: %s\n", $1.text);
  1962.                 >>
  1963.             )
  1964.         ;
  1965.  
  1966.  
  1967.  
  1968.  
  1969.  
  1970.  
  1971.  
  1972.  
  1973.  
  1974.  
  1975.  
  1976.  
  1977.  
  1978.  
  1979.  
  1980.  
  1981.  
  1982.  
  1983.                                                                Page 32
  1984.  
  1985. PCCTS Advanced Tutorial 1.0x
  1986.  
  1987.  
  1988.  
  1989. func    :   <<Sym *locals=NULL, *var, *p; current_local_var_offset = 0;>>
  1990.             WORD
  1991.             <<zzs_scope(&globals);
  1992.               var = zzs_newadd($1.text);
  1993.               var->level = GLOBAL;
  1994.               var->token = FUNC;
  1995.  
  1996.               if (strcmp("main",$1.text)) { printf("%s()\n",$1.text); }
  1997.               else printf("_main()\n");
  1998.             >>
  1999.             "\(" (  def[&locals, PARAMETER]
  2000.                  |  <<current_local_var_offset = 1;>>
  2001.                  )
  2002.             "\)"
  2003.             "\{" << printf("{\n\tBEGIN;\n"); >>
  2004.                 ( "var" def[&locals, LOCAL] ";" )*
  2005.                 ( statement )*
  2006.             "\}" << printf("\tEND;\n}\n"); >>
  2007.             <<  p = zzs_rmscope(&locals); >>
  2008.         ;
  2009.  
  2010. statement : <<int n;>>
  2011.             expr ";"            <<printf("\tPOP;\n");>>
  2012.         |   "\{" ( statement )* "\}"
  2013.         |   "if" "\(" expr "\)" << n = LabelNum++;
  2014.                                    printf("\tBRF(iflabel%d);\n",n); >>
  2015.                 statement       << printf("iflabel%d: ;\n",n); >>
  2016.             {"else" statement}
  2017.         |
  2018.             "while"             << n = LabelNum++;
  2019.                                    printf("wbegin%d: ;\n", n); >>
  2020.             "\(" expr "\)"      << printf("\tBRF(wend%d);\n",n); >>
  2021.             statement           << printf("\tBR(wbegin%d);\n", n); >>
  2022.                                 << printf("wend%d: ;\n",n); >>
  2023.                                 << n++; >>
  2024.         |   "return" expr ";"   << printf("\tRETURN;\n"); >>
  2025.         |   "print" expr ";"    << printf("\tPRINT;\n"); >>
  2026.         ;
  2027.  
  2028.  
  2029.  
  2030.  
  2031.  
  2032.  
  2033.  
  2034.  
  2035.  
  2036.  
  2037.  
  2038.  
  2039.  
  2040.  
  2041.  
  2042.  
  2043.  
  2044.  
  2045.                                                                Page 33
  2046.  
  2047. PCCTS Advanced Tutorial 1.0x
  2048.  
  2049.  
  2050.  
  2051. expr    :   <<Sym *s;>>
  2052.             VAR "=" expr        << printf("\tDUP;\n"); >>
  2053.             <<s = zzs_get($1.text);
  2054.               if ( s->level != GLOBAL )
  2055.                 printf("\tLSTORE(%d);\n", s->offset);
  2056.               else printf("\tSTORE(%s);\n", s->symbol);
  2057.             >>
  2058.         |   expr0
  2059.         ;
  2060.  
  2061. expr0   :   <<char *op;>>
  2062.             expr1 ( (   "==" <<op="EQ";>>
  2063.                     |   "!=" <<op="NEQ";>>
  2064.                     )
  2065.                     expr1
  2066.                     <<printf("\t%s;\n", op);>>
  2067.                   )*
  2068.         ;
  2069.  
  2070. expr1   :   <<char *op;>>
  2071.             expr2 ( (   "\+" <<op="ADD";>>
  2072.                     |   "\-" <<op="SUB";>>
  2073.                     )
  2074.                     expr2
  2075.                     <<printf("\t%s;\n", op);>>
  2076.                   )*
  2077.         ;
  2078.  
  2079. expr2   :   <<char *op;>>
  2080.             expr3 ( (   "\*" <<op="MUL";>>
  2081.                     |   "/"  <<op="DIV";>>
  2082.                     )
  2083.                     expr3
  2084.                     <<printf("\t%s;\n", op);>>
  2085.                   )*
  2086.         ;
  2087.  
  2088.  
  2089.  
  2090.  
  2091.  
  2092.  
  2093.  
  2094.  
  2095.  
  2096.  
  2097.  
  2098.  
  2099.  
  2100.  
  2101.  
  2102.  
  2103.  
  2104.  
  2105.  
  2106.  
  2107.                                                                Page 34
  2108.  
  2109. PCCTS Advanced Tutorial 1.0x
  2110.  
  2111.  
  2112.  
  2113. expr3   :   <<char *op=NULL;>>
  2114.             {"\-" <<op="NEG";>>} expr4
  2115.             <<if ( op!=NULL ) printf("\t%s;\n", op);>>
  2116.         ;
  2117.  
  2118. expr4   :   <<Sym *s; int arg;>>
  2119.             STRING   << printf("\tSPUSH(%s);\n", $1.text); >>
  2120.         |   VAR     << s = zzs_get($1.text);
  2121.                        if ( s->level != GLOBAL )
  2122.                             printf("\tLPUSH(%d);\n", s->offset);
  2123.                        else printf("\tPUSH(%s);\n", s->symbol);
  2124.                     >>
  2125.         |   (   FUNC    <<$0=$1;>>
  2126.             |   WORD    <<$0=$1;>>
  2127.             )
  2128.             "\(" { <<arg=0;>> expr <<arg=1;>> } "\)"
  2129.             <<if ( !arg ) printf("\tSPUSH(\"\");\n");
  2130.               printf("\tCALL(%s);\n", $1.text);>>
  2131.         |   "\(" expr "\)"
  2132.     ;
  2133.  
  2134. #token WORD "[a-zA-Z]+"
  2135.     <<{
  2136.         Sym *p = zzs_get(zzlextext);
  2137.         if ( p != NULL ) NLA = p->token;
  2138.     }>>
  2139.  
  2140.  
  2141.  
  2142. 3.5.  Makefile for Full Translator
  2143.  
  2144.      The makefile is no different from the one  used  for  the  symbol
  2145. table management version of the tutorial except that we need to change
  2146. the GRM make variable as follows:
  2147.  
  2148.  
  2149. GRM=tut3
  2150.  
  2151.  
  2152.  
  2153. which implies that tut3.g is the file containing the third revision of
  2154. our sc translator.
  2155.  
  2156. 3.6.  Use of translator
  2157.  
  2158.      Once the translator has been made using the makefile, it is ready
  2159. to  translate  sc  programs.   To  translate and execute the factorial
  2160. example from above, we execute the following:
  2161.  
  2162.  
  2163. tut3 < fact.c > temp.c
  2164.  
  2165.  
  2166.  
  2167.  
  2168.  
  2169.                                                                Page 35
  2170.  
  2171. PCCTS Advanced Tutorial 1.0x
  2172.  
  2173.  
  2174. where fact.c is the file containing the factorial code.   temp.c  will
  2175. contain  the  translated  program.   It  is valid C code because it is
  2176. nothing more than a bunch of macro invocations (the macros are defined
  2177. in sc.h).  We can compile temp.c like any other C program:
  2178.  
  2179.  
  2180. cc temp.c
  2181.  
  2182.  
  2183.  
  2184. To execute the program, we type:
  2185.  
  2186.  
  2187. a.out n
  2188.  
  2189.  
  2190.  
  2191. where n is the number you want the factorial of.  Typing:
  2192.  
  2193.  
  2194. a.out 8
  2195.  
  2196.  
  2197.  
  2198. yields:
  2199.  
  2200.  
  2201. 40320.000000
  2202.  
  2203.  
  2204.  
  2205. 3.7.  Stack code macros - sc.h
  2206.  
  2207.      The following file is included by any C program using  the  stack
  2208. code instructions outlined above.
  2209.  
  2210.  
  2211.  
  2212.  
  2213.  
  2214.  
  2215.  
  2216.  
  2217.  
  2218.  
  2219.  
  2220.  
  2221.  
  2222.  
  2223.  
  2224.  
  2225.  
  2226.  
  2227.  
  2228.  
  2229.  
  2230.  
  2231.                                                                Page 36
  2232.  
  2233. PCCTS Advanced Tutorial 1.0x
  2234.  
  2235.  
  2236.  
  2237. /* sc.h -- string C stack machine macros
  2238.  *
  2239.  * For use with PCCTS advanced tutorial version 1.0x
  2240.  */
  2241. #include <stdio.h>
  2242. #include <ctype.h>
  2243. #include <math.h>
  2244.  
  2245. /*
  2246.  * The function invocation stack looks like:
  2247.  *
  2248.  *  |   .               |
  2249.  *  |   .               |
  2250.  *  |   arg             |       fp + 0          arg is "" if none specified
  2251.  *  | 1st local |       fp - 1
  2252.  *  | 2nd local |       fp - 2
  2253.  *  |   ...             |
  2254.  *  |   .               |
  2255.  *  |   .               |
  2256.  */
  2257.  
  2258.  
  2259.  
  2260.  
  2261. #define STR_SIZE                100
  2262. #define STK_SIZE                200
  2263. /* define stack */
  2264. typedef struct { char text[STR_SIZE]; } SCVAR;
  2265. static SCVAR stack[STK_SIZE];
  2266. static int sp = STK_SIZE, fp;
  2267.  
  2268. /* number begins with number or '.' followed by number.  All numbers
  2269.  * are converted to floats before comparison.
  2270.  */
  2271. #define SCnumber(a)     (isdigit(a[0]) || (a[0]=='.' && isdigit(a[1])))
  2272.  
  2273.  
  2274.  
  2275.  
  2276.  
  2277.  
  2278.  
  2279.  
  2280.  
  2281.  
  2282.  
  2283.  
  2284.  
  2285.  
  2286.  
  2287.  
  2288.  
  2289.  
  2290.  
  2291.  
  2292.  
  2293.                                                                Page 37
  2294.  
  2295. PCCTS Advanced Tutorial 1.0x
  2296.  
  2297.  
  2298.  
  2299. #define TOS                     stack[sp].text
  2300. #define NTOS            stack[sp+1].text
  2301. #define TOSTRUE         ((strcmp(TOS, "true")==0)||(strcmp(TOS, "1")==0)        \
  2302.                                         ||(SCnumber(TOS)&&atof(TOS)==1.0) )
  2303. #define TOSFALSE        ((strcmp(TOS, "false")==0)||(strcmp(TOS, "0")==0)       \
  2304.                                         ||(SCnumber(TOS)&&atof(TOS)==0.0) )
  2305.  
  2306. #define PUSH(a)         {if ( sp==0 ) {fprintf(stderr, "stk ovf!\n"); exit(-1);} \
  2307.                                         strcpy(stack[--sp].text, (a).text);}
  2308.  
  2309. #define SPUSH(a)        {if ( sp==0 ) {fprintf(stderr, "stk ovf!\n"); exit(-1);} \
  2310.                                         strcpy(stack[--sp].text, a);}
  2311.  
  2312. #define LPUSH(a)        {if ( sp==0 ) {fprintf(stderr, "stk ovf!\n"); exit(-1);} \
  2313.                                         stack[--sp] = stack[fp-a];}
  2314.  
  2315.  
  2316.  
  2317.  
  2318. #define CALL(f)         {f();}
  2319.  
  2320. #define POP                     stack[sp++]
  2321.  
  2322. #define LOCAL           {if ( sp==0 ) {fprintf(stderr, "stk ovf!\n"); exit(-1);} \
  2323.                                         stack[--sp].text[0] = '\0';}
  2324.  
  2325.  
  2326.  
  2327.  
  2328. #define BRF(lab)        if ( TOSFALSE ) {POP; goto lab;} else POP;
  2329. #define BRT(lab)        if ( TOSTRUE ) {POP; goto lab;} else POP;
  2330. #define BR(lab)         goto lab
  2331.  
  2332. #define PRINT           printf("%s", POP.text)
  2333.  
  2334. #define RETURN          {strcpy(stack[fp].text, TOS); END; return;}
  2335.  
  2336. #define STORE(v)        {v = POP;}
  2337. #define LSTORE(off)     {stack[fp-off] = POP;}
  2338.  
  2339.  
  2340.  
  2341.  
  2342.  
  2343.  
  2344.  
  2345.  
  2346.  
  2347.  
  2348.  
  2349.  
  2350.  
  2351.  
  2352.  
  2353.  
  2354.  
  2355.                                                                Page 38
  2356.  
  2357. PCCTS Advanced Tutorial 1.0x
  2358.  
  2359.  
  2360.  
  2361. /* operators */
  2362.  
  2363. #define EQ                      {char *a,*b; float c,d;                         \
  2364.                                         a = POP.text; b = POP.text;             \
  2365.                                         if ( SCnumber(a) && SCnumber(b) ) {     \
  2366.                                                 c=atof(a); d=atof(b);           \
  2367.                                                 if ( c == d ) {SPUSH("true");}  \
  2368.                                             else SPUSH("false");                \
  2369.                                         }                                       \
  2370.                                         else if ( strcmp(a, b)==0 ) {SPUSH("true");}\
  2371.                                              else SPUSH("false");}
  2372. #define NEQ                     {SCVAR a,b; float c,d;                          \
  2373.                                         a = POP.text; b = POP.text;             \
  2374.                                         if ( SCnumber(a) && SCnumber(b) ) {     \
  2375.                                                 c=atof(a); d=atof(b);           \
  2376.                                                 if ( c != d ) {SPUSH("true");}  \
  2377.                                             else SPUSH("false");                \
  2378.                                         }                                       \
  2379.                                         else if ( strcmp(a, b)!=0 ) {SPUSH("true");}\
  2380.                                              else SPUSH("false");}
  2381. #define ADD                     {SCVAR c; float a,b;                            \
  2382.                                         if ( !SCnumber(NTOS) || !SCnumber(TOS) ) { \
  2383.                                                 strncat(NTOS, TOS, STR_SIZE - strlen(NTOS));\
  2384.                                                 sp++;                           \
  2385.                                         } else {                                \
  2386.                                                 a=atof(POP.text); b=atof(POP.text);\
  2387.                                                 sprintf(c.text, "%f", a+b); PUSH(c);\
  2388.                                         }}
  2389. #define SUB                     {SCVAR c; float a,b; a=atof(POP.text); b=atof(POP.text); \
  2390.                                         sprintf(c.text, "%f", b-a); PUSH(c);}
  2391. #define MUL                     {SCVAR c; float a,b; a=atof(POP.text); b=atof(POP.text); \
  2392.                                         sprintf(c.text, "%f", a*b); PUSH(c);}
  2393. #define DIV                     {SCVAR c; float a,b; a=atof(POP.text); b=atof(POP.text); \
  2394.                                         sprintf(c.text, "%f", b/a); PUSH(c);}
  2395. #define NEG                     {SCVAR c; float a; a=atof(POP.text); \
  2396.                                         sprintf(c.text, "%f", -a); PUSH(c);}
  2397. #define DUP                     {if ( sp==0 ) {fprintf(stderr, "stk ovf!\n"); exit(-1);} \
  2398.                                         stack[sp-1] = stack[sp]; --sp;}
  2399.  
  2400.  
  2401.  
  2402.  
  2403.  
  2404.  
  2405.  
  2406.  
  2407.  
  2408.  
  2409.  
  2410.  
  2411.  
  2412.  
  2413.  
  2414.  
  2415.  
  2416.  
  2417.                                                                Page 39
  2418.  
  2419. PCCTS Advanced Tutorial 1.0x
  2420.  
  2421.  
  2422.  
  2423. #define BEGIN           int save_fp = fp; fp = sp
  2424. #define END                     sp = fp; fp = save_fp;
  2425.  
  2426. main(argc, argv)
  2427. int argc;
  2428. char *argv[];
  2429. {
  2430.         if ( argc == 2 ) {SPUSH(argv[1]);}
  2431.         else SPUSH("");
  2432.         CALL(_main);
  2433.         POP;
  2434. }
  2435.  
  2436.  
  2437.  
  2438. 4.  Intermediate form construction
  2439.  
  2440.      This section describes how trees can be used as  an  intermediate
  2441. form  of the sc source program and how our tut2.g symbol table manage-
  2442. ment example can be modified to construct these trees.   Example  tree
  2443. constructions are given as well as the complete source.
  2444.  
  2445.         Note that this section and the code generation section  essen-
  2446. tially  duplicate  the translation achieved in the previous section on
  2447. stack code.  We arrive at the solution from a  different  angle,  how-
  2448. ever.   This  method is much more general and would be used for "real"
  2449. grammars.
  2450.  
  2451. 4.1.  Tree Construction
  2452.  
  2453.      To construct an intermediate form (IF) representation  of  an  sc
  2454. program,  we will construct trees using the abstract syntax tree (AST)
  2455. mechanism provided with PCCTS.  PCCTS supports  an  automatic  and  an
  2456. explicit  tree construction mechanism; we will use both.  We will aug-
  2457. ment the grammar  that  has  the  symbol  table  management  actions -
  2458. tut2.g.
  2459.  
  2460.      In order to use the AST mechanism within PCCTS, we  must  do  the
  2461. following:
  2462.  
  2463. o    Define the AST fields, AST_FIELDS, needed by the user.
  2464.  
  2465. o    Define the default AST node constructor,  zzcr_ast(),  that  con-
  2466.      verts from a lexeme to an AST node.
  2467.  
  2468. o    Define an explicit AST node constructor - zzmk_ast() (because  we
  2469.      use the explicit tree constructor mechanism also).
  2470.  
  2471.      Our tree nodes will contain a token number to identify the  node.
  2472. This  token  number  can  also  be  a  value  for  which  there  is no
  2473. corresponding lexical item (e.g. a  function  call  may  have  a  node
  2474. called  DefineVar).  If the token indicates that the node represents a
  2475. variable or function, we must have information as to its level, offset
  2476.  
  2477.  
  2478.  
  2479.                                                                Page 40
  2480.  
  2481. PCCTS Advanced Tutorial 1.0x
  2482.  
  2483.  
  2484. from  the  frame  pointer  (if  a  local  or parameter) and the string
  2485. representing the name of the item.  This information can all  be  held
  2486. via:
  2487.  
  2488.  
  2489. #define AST_FIELDS int token, level, offset; char str[D_TextSize];
  2490.  
  2491.  
  2492.  
  2493. which will be added to the #header PCCTS pseudo-op action.  Note  that
  2494. D_TextSize is defined in charbuf.h.
  2495.  
  2496.      To tell PCCTS how it should build AST  nodes  for  use  with  the
  2497. automatic  tree  construction mechanism, we define the following macro
  2498. in the #header action:
  2499.  
  2500.  
  2501. #define zzcr_ast(ast,attr,tok,text) create_ast(ast,attr,tok,text)
  2502.  
  2503.  
  2504.  
  2505. which merely calls a function we define as follows:
  2506.  
  2507.  
  2508. create_ast(ast,attr,tok,text)
  2509. AST *ast;
  2510. Attrib *attr;
  2511. int tok;
  2512. char *text;
  2513. {
  2514.     Sym *s;
  2515.  
  2516.     ast->token = tok;
  2517.     if ( tok == VAR )
  2518.     {
  2519.         s = zzs_get(text);
  2520.         ast->level = s->level;
  2521.         ast->offset = s->offset;
  2522.     }
  2523.     if ( tok == STRING || tok == VAR || tok == FUNC ) strcpy(ast->str, text);
  2524. }
  2525.  
  2526.  
  2527.  
  2528. Because of the symbol table lookup etc... we make the node constructor
  2529. a  function rather than have the code replicated at each invocation of
  2530. the zzcr_ast macro.
  2531.  
  2532.      When we explicitly construct trees, the automatic node  construc-
  2533. tor  is  generally  disabled and we must explicitly call a function to
  2534. create an AST node:
  2535.  
  2536.  
  2537.  
  2538.  
  2539.  
  2540.  
  2541.                                                                Page 41
  2542.  
  2543. PCCTS Advanced Tutorial 1.0x
  2544.  
  2545.  
  2546.  
  2547. AST *
  2548. zzmk_ast(node, token, str)
  2549. AST *node;
  2550. int token;
  2551. char *str;
  2552. {
  2553.     Sym *s;
  2554.  
  2555.     node->token = token;
  2556.     if ( token == VAR )
  2557.     {
  2558.         s = zzs_get(str);
  2559.         node->level = s->level;
  2560.         node->offset = s->offset;
  2561.     }
  2562.     if ( tok == STRING || tok == VAR || tok == FUNC )
  2563.                 strcpy(node->str, str);
  2564.     return node;
  2565. }
  2566.  
  2567.  
  2568. This function will be invoked when we have a  grammar  action  with  a
  2569. reference of the form #[token, string].
  2570.  
  2571.      In order to print out the trees that  we  have  defined,  let  us
  2572. define  a  simple  function  to  do  a preorder, lisp-like walk of our
  2573. trees:
  2574.  
  2575.  
  2576. lisp(tree)
  2577. AST *tree;
  2578. {
  2579.     while ( tree!= NULL )
  2580.     {
  2581.         if ( tree->down != NULL ) printf(" (");
  2582.         if ( tree->token == STRING ||
  2583.              tree->token == VAR ||
  2584.              tree->token == FUNC ) printf(" %s", tree->str);
  2585.         else printf(" %s", zztokens[tree->token]);
  2586.         lisp(tree->down);
  2587.         if ( tree->down != NULL ) printf(" )");
  2588.         tree = tree->right;
  2589.     }
  2590. }
  2591.  
  2592.  
  2593.  
  2594.      PCCTS automatically assumes that all rules will produce trees and
  2595. that  all  terminals  within  rules  will result in nodes added to the
  2596. current tree.  In the case of rules p, expr4, statement and func, this
  2597. is  not true.  We will explicitly handle the trees within these rules.
  2598. Therefore, we append a ! after the definition of these rules.  We need
  2599. to  decide  how  each sc construct will be translated to a subtree and
  2600.  
  2601.  
  2602.  
  2603.                                                                Page 42
  2604.  
  2605. PCCTS Advanced Tutorial 1.0x
  2606.  
  2607.  
  2608. when we will pass these trees off to the code generator.  We will col-
  2609. lect  all  subtrees  within a function and then, just before we remove
  2610. the symbols for that function, we will pass this tree off to  lisp  to
  2611. be  printed;  we will pass it off to the code generator when we define
  2612. it in the next section.  After it has been printed, the function trees
  2613. will be destroyed.  For global variable definitions, we will pass each
  2614. one individually off to lisp and then destroy the tree.
  2615.  
  2616.      Before modifying the rules of the grammar, we must define  labels
  2617. for  a  number  of regular expressions so that the token value of that
  2618. expression can be referenced from within an action.   We  also  define
  2619. labels  for tokens which do not exist physically in a program, but are
  2620. needed for code generation.
  2621.  
  2622.  
  2623. /* Not actual terminals, just node identifiers */
  2624. #token DefineFunc
  2625. #token SLIST
  2626.  
  2627.  
  2628.  
  2629.  
  2630. /* Define tokens for code generation */
  2631. #token DefineVar    "var"
  2632. #token Mul          "
  2633. #token Div          "/"
  2634. #token Add          "+"
  2635. #token Sub          "-"
  2636. #token Equal        "=="
  2637. #token NotEqual     "!="
  2638. #token If           "if"
  2639. #token While        "while"
  2640. #token Return       "return"
  2641. #token Print        "print"
  2642. #token Assign       "="
  2643.  
  2644.  
  2645.  
  2646.      All PCCTS grammars that use the AST mechanism need  to  pass  the
  2647. address of a NULL pointer to the starting rule.
  2648.  
  2649.  
  2650. main()
  2651. {
  2652.     AST *root=NULL;
  2653.  
  2654.     zzs_init(HashTableSize, StringTableSize);
  2655.     ANTLR(p(&root), stdin);
  2656. }
  2657.  
  2658.  
  2659.  
  2660.      Rule p is modified as follows:
  2661.  
  2662.  
  2663.  
  2664.  
  2665.                                                                Page 43
  2666.  
  2667. PCCTS Advanced Tutorial 1.0x
  2668.  
  2669.  
  2670.  
  2671. p!      :   <<Sym *p; AST *v;>>
  2672.             (   func
  2673.             |   "var" def[&globals, GLOBAL] ";"
  2674.                 <<v = #(#[DefineVar], #2);
  2675.                   lisp(v); printf("\n"); zzfree_ast(v);
  2676.                 >>
  2677.             )*
  2678.             <<p = zzs_rmscope(&globals);>>
  2679.             "@"
  2680.         ;
  2681.  
  2682.  
  2683.  
  2684. The #[DefineVar] reference calls our zzmk_ast macro to create  an  AST
  2685. node   whose   token   is   set   to   DefineVar.   The  reference  to
  2686. #(#[DefineVar], #2) is a tree constructor which  makes  the  DefineVar
  2687. node  the  parent  of the tree returned by rule def - #2.  In general,
  2688. the tree constructor has the form:
  2689.  
  2690.  
  2691. #( root, sibling1, sibling2, ..., siblingN )
  2692.  
  2693.  
  2694.  
  2695. where any NULL  pointer  terminates  the  list  except  for  the  root
  2696. pointer.  #2  refers  to  the  second  AST  node  or  tree  within  an
  2697. alternative - def in our  case.   Rule  def  itself  does  not  change
  2698. because  PCCTS  automatically  creates  a node for the WORD or VAR and
  2699. passes it back to the invoking rule.
  2700.  
  2701.      Trees for functions are constructed in the following form:
  2702.  
  2703.  
  2704.      DefineFunc
  2705.          |
  2706.          v
  2707.         FUNC -> DefineVar -> DefineVar -> SLIST
  2708.                     |            |          |
  2709.                     v            |          v
  2710.               optional_arg       |        stat1 -> ... > statn
  2711.                                  v
  2712.                                local1 -> ... -> localn
  2713.  
  2714.  
  2715.  
  2716. where DefineFunc and DefineVar are dummy tokens used only in trees (as
  2717. opposed to the grammar).  Rule func is modified to build these trees:
  2718.  
  2719.  
  2720.  
  2721.  
  2722.  
  2723.  
  2724.  
  2725.  
  2726.  
  2727.                                                                Page 44
  2728.  
  2729. PCCTS Advanced Tutorial 1.0x
  2730.  
  2731.  
  2732.  
  2733. func!  :  <<Sym *locals=NULL, *var, *p; AST *f,*parm=NULL,*v=NULL,*s=NULL;
  2734.               current_local_var_offset = 0;>>
  2735.             WORD
  2736.             <<zzs_scope(&globals);
  2737.               var = zzs_newadd($1.text);
  2738.               var->level = GLOBAL;
  2739.               var->token = FUNC;
  2740.             >>
  2741.             "\(" (  def[&locals, PARAMETER] <<parm=#1;>>
  2742.                  |  <<current_local_var_offset = 1;>>
  2743.                  )
  2744.             "\)"
  2745.             "\{"
  2746.                 ( "var" def[&locals, LOCAL]
  2747.                   <<if ( v==NULL ) v = #2; else v = #(NULL,v,#2);>>
  2748.                   ";"
  2749.                 )*
  2750.                 ( statement
  2751.                   <<if ( s==NULL ) s = #1; else s = #(NULL,s,#1);>>
  2752.                 )*
  2753.             "\}"
  2754.             <<s = #(#[SLIST], s);
  2755.               v = #(#[DefineVar], v);
  2756.               parm = #(#[DefineVar], parm);
  2757.               f = #(#[DefineFunc], #[FUNC,$1.text], parm, v, s);
  2758.               lisp(f); printf("\en"); zzfree_ast(f);
  2759.               p = zzs_rmscope(&locals);>>
  2760.         ;
  2761.  
  2762.  
  2763.  
  2764. Variable parm is set to the AST node created by def if a parameter  is
  2765. found else it is NULL.  Variable v is used to maintain a list of local
  2766. variables.  The tree constructor
  2767.  
  2768.  
  2769. v = #(NULL,v,#2);
  2770.  
  2771.  
  2772.  
  2773. says to make a new tree with no root and  with  siblings  v  and  #2 -
  2774. which  effectively  links  #2  to the end of the current list of vari-
  2775. ables.  Variable s behaves in a similar fashion.  After  the  list  of
  2776. variables  and  statements  have been accumulated, we add a dummy node
  2777. (DefineVar, SLIST) as a root to each list so that we get the structure
  2778. given above.  To examine the trees we have constructed, we make a call
  2779. to lisp and then destroy the tree.
  2780.  
  2781.      Even though it is not necessary to do so, we will build trees for
  2782. statement  explicitly (in general, the automatic mechanism is best for
  2783. expressions with simple operator/operand relationships).
  2784.  
  2785.  
  2786.  
  2787.  
  2788.  
  2789.                                                                Page 45
  2790.  
  2791. PCCTS Advanced Tutorial 1.0x
  2792.  
  2793.  
  2794.  
  2795. statement!: <<AST *s=NULL, *el=NULL;>>
  2796.             expr ";"                          <<#0 = #1;>>
  2797.         |   "\{"
  2798.                 ( statement
  2799.                   <<if ( s==NULL ) s = #1; else s = #(NULL,s,#1);>>
  2800.                 )*
  2801.             "\}" <<#0 = #(#[SLIST], s);>>
  2802.         |   "if" "\(" expr "\)" statement
  2803.             {"else" statement <<el=#2;>>}     <<#0 = #(#[If], #3, #5,el);>>
  2804.         | "while" "\(" expr "\)" statement    <<#0 = #(#[While], #3,#5);>>
  2805.         | "return" expr ";"                   <<#0 = #(#[Return], #2);>>
  2806.         | "print" expr ";"                    <<#0 = #(#[Print], #2);>>
  2807.         ;
  2808.  
  2809.  
  2810.  
  2811. Many of the tokens in statement are not included in the  tree  because
  2812. they  are a notational convenience for humans or are used for grouping
  2813. purposes.  As before, we track lists of statements using the tree con-
  2814. structor: #(NULL,s,#1).
  2815.  
  2816.      The last unusual rule is expr:
  2817.  
  2818.  
  2819. expr4!  :   <<AST *f=NULL, *arg=NULL;>>
  2820.             STRING          <<#0 = #[STRING, $1.text];>>
  2821.         |   VAR             <<#0 = #[STRING, $1.text];>>
  2822.         |   (   FUNC        <<f  = #[FUNC, $1.text];>>
  2823.             |   WORD        <<f  = #[FUNC, $1.text];>>
  2824.             )
  2825.             "\(" { expr <<arg=#1;>> } "\)"
  2826.             <<#0 = #(f, arg);>>
  2827.         |   "\(" expr "\)"  <<#0 = #2;>>
  2828.         ;
  2829.  
  2830.  
  2831.  
  2832. Assigning a tree to #0 makes that tree the return tree.   However,  it
  2833. should really only be used in rules that do not use the automatic tree
  2834. construction mechanism; i.e. there is a ! after the  rule  definition.
  2835. For  a  function call, we make a tree with a FUNC node at the root and
  2836. the optional argument as the  child.   The  third  alternative  merely
  2837. returns  what  is  computed by expr; the parenthesis are mechanism for
  2838. syntactic precedence and add nothing to the tree.  The tree  structure
  2839. itself embodies the precedence.
  2840.  
  2841.      The only other required modifications to the grammar are to indi-
  2842. cate which tokens are operators (subtree roots) and which are operands
  2843. in the expression rules.  To indicate that a token is  to  be  made  a
  2844. subtree root, we append a ^.  All other tokens are considered operands
  2845. (children).  Appending a token with ! indicates that it is not  to  be
  2846. included in the tree.  For example, to make trees like:
  2847.  
  2848.  
  2849.  
  2850.  
  2851.                                                                Page 46
  2852.  
  2853. PCCTS Advanced Tutorial 1.0x
  2854.  
  2855.  
  2856.  
  2857.         operator
  2858.             |
  2859.             v
  2860.           opnd1 -> opnd2
  2861.  
  2862.  
  2863.  
  2864. we modify the operators in expr through expr3 in a fashion similar to:
  2865.  
  2866.  
  2867. expr1   :   expr2 ( (   "\+"^
  2868.                     |   "\-"^
  2869.                     )
  2870.                     expr2
  2871.                   )*
  2872.         ;
  2873.  
  2874.  
  2875.  
  2876. and
  2877.  
  2878.  
  2879. expr3   :   { "\-"^ } expr4
  2880.         ;
  2881.  
  2882.  
  2883.  
  2884. 4.2.  Full Grammar to Construct Trees
  2885.  
  2886.      The following grammar constructs AST's as  an  intermediate  form
  2887. (IF) of an sc program and prints out the IF in lisp-like preorder.
  2888.  
  2889.  
  2890. #header <<#include "sym.h"
  2891.           #include "charbuf.h"
  2892.           #define AST_FIELDS int token, level, offset; char str[D_TextSize];
  2893.           #define zzcr_ast(ast,attr,tok,text) create_ast(ast,attr,tok,text)
  2894.           #define DONT_CARE         0
  2895.           #define SIDE_EFFECTS      1
  2896.           #define VALUE             2
  2897.         >>
  2898.  
  2899. #token "[\t\ ]+"    << zzskip(); >>                /* Ignore White */
  2900. #token "\n"         << zzline++; zzskip(); >>
  2901. #token STRING "\"(~[\0-\0x1f\"\\]|(\\~[\0-\0x1f]))*\"" <<;>>
  2902.  
  2903. /* Not actual terminals, just node identifiers */
  2904. #token DefineFunc
  2905. #token SLIST
  2906.  
  2907.  
  2908.  
  2909.  
  2910.  
  2911.  
  2912.  
  2913.                                                                Page 47
  2914.  
  2915. PCCTS Advanced Tutorial 1.0x
  2916.  
  2917.  
  2918.  
  2919. /* Define tokens for code generation */
  2920. #token DefineVar    "var"
  2921. #token Mul          "\*"
  2922. #token Div          "/"
  2923. #token Add          "\+"
  2924. #token Sub          "\-"
  2925. #token Equal        "=="
  2926. #token NotEqual     "!="
  2927. #token If           "if"
  2928. #token While        "while"
  2929. #token Return       "return"
  2930. #token Print        "print"
  2931. #token Assign       "="
  2932.  
  2933. <<;>>
  2934.  
  2935. <<
  2936. #define HashTableSize       999
  2937. #define StringTableSize     5000
  2938. #define GLOBAL              0
  2939. #define PARAMETER           1
  2940. #define LOCAL               2
  2941.  
  2942.  
  2943.  
  2944.  
  2945. static Sym *globals = NULL; /* global scope for symbols */
  2946. static int current_local_var_offset=0;
  2947.  
  2948. create_ast(ast,attr,tok,text)
  2949. AST *ast;
  2950. Attrib *attr;
  2951. int tok;
  2952. char *text;
  2953. {
  2954.     Sym *s;
  2955.  
  2956.     ast->token = tok;
  2957.     if ( tok == VAR )
  2958.     {
  2959.         s = zzs_get(text);
  2960.         ast->level = s->level;
  2961.         ast->offset = s->offset;
  2962.     }
  2963.     if ( tok == STRING || tok == VAR || tok == FUNC ) strcpy(ast->str, text);
  2964. }
  2965.  
  2966.  
  2967.  
  2968.  
  2969.  
  2970.  
  2971.  
  2972.  
  2973.  
  2974.  
  2975.                                                                Page 48
  2976.  
  2977. PCCTS Advanced Tutorial 1.0x
  2978.  
  2979.  
  2980.  
  2981. AST *
  2982. zzmk_ast(node, token, str)
  2983. AST *node;
  2984. int token;
  2985. char *str;
  2986. {
  2987.     Sym *s;
  2988.  
  2989.     node->token = token;
  2990.     if ( token == VAR )
  2991.     {
  2992.         s = zzs_get(str);
  2993.         node->level = s->level;
  2994.         node->offset = s->offset;
  2995.     }
  2996.     if ( token == STRING || token == VAR || token == FUNC )
  2997.         strcpy(node->str, str);
  2998.     return node;
  2999. }
  3000.  
  3001.  
  3002.  
  3003.  
  3004. lisp(tree)
  3005. AST *tree;
  3006. {
  3007.     while ( tree!= NULL )
  3008.     {
  3009.         if ( tree->down != NULL ) printf(" (");
  3010.         if ( tree->token == STRING ||
  3011.              tree->token == VAR ||
  3012.              tree->token == FUNC ) printf(" %s", tree->str);
  3013.         else printf(" %s", zztokens[tree->token]);
  3014.         lisp(tree->down);
  3015.         if ( tree->down != NULL ) printf(" )");
  3016.         tree = tree->right;
  3017.     }
  3018. }
  3019.  
  3020. main()
  3021. {
  3022.     AST *root=NULL;
  3023.  
  3024.     zzs_init(HashTableSize, StringTableSize);
  3025.     ANTLR(p(&root), stdin);
  3026. }
  3027.  
  3028.  
  3029.  
  3030.  
  3031.  
  3032.  
  3033.  
  3034.  
  3035.  
  3036.  
  3037.                                                                Page 49
  3038.  
  3039. PCCTS Advanced Tutorial 1.0x
  3040.  
  3041.  
  3042.  
  3043. pScope(p)
  3044. Sym *p;
  3045. {
  3046.     for (; p!=NULL; p=p->scope)
  3047.     {
  3048.         printf("\tlevel %d | %-12s | %-15s\n",
  3049.             p->level,
  3050.             zztokens[p->token],
  3051.             p->symbol);
  3052.     }
  3053. }
  3054. >>
  3055.  
  3056. p!      :   <<Sym *p; AST *v;>>
  3057.             (   func
  3058.             |   "var" def[&globals, GLOBAL] ";"
  3059.                 <<v = #(#[DefineVar], #2);
  3060.                   gen(v,DONT_CARE); printf("\n"); zzfree_ast(v);
  3061.                 >>
  3062.             )*
  3063.             <<p = zzs_rmscope(&globals);>>
  3064.             "@"
  3065.         ;
  3066.  
  3067.  
  3068.  
  3069.  
  3070.  
  3071.  
  3072.  
  3073.  
  3074.  
  3075.  
  3076.  
  3077.  
  3078.  
  3079.  
  3080.  
  3081.  
  3082.  
  3083.  
  3084.  
  3085.  
  3086.  
  3087.  
  3088.  
  3089.  
  3090.  
  3091.  
  3092.  
  3093.  
  3094.  
  3095.  
  3096.  
  3097.  
  3098.  
  3099.                                                                Page 50
  3100.  
  3101. PCCTS Advanced Tutorial 1.0x
  3102.  
  3103.  
  3104.  
  3105. def[Sym **scope, int level]
  3106.         :   <<Sym *var;>>
  3107.             (   WORD
  3108.                 <<zzs_scope($scope);
  3109.                   var = zzs_newadd($1.text);
  3110.                   var->level = $level;
  3111.                   var->token = VAR;
  3112.                   var->offset = current_local_var_offset++;
  3113.                 >>
  3114.             |   VAR
  3115.                 <<var = zzs_get($1.text);
  3116.                   if ( $level != var->level )
  3117.                   {
  3118.                     zzs_scope($scope);
  3119.                     var = zzs_newadd($1.text);
  3120.                     var->level = $level;
  3121.                     var->token = VAR;
  3122.                     var->offset = current_local_var_offset++;
  3123.                   }
  3124.                   else printf("redefined variable ignored: %s\n", $1.text);
  3125.                 >>
  3126.             )
  3127.         ;
  3128.  
  3129. func!   :   <<Sym *locals=NULL, *var, *p; AST *f,*parm=NULL,*v=NULL,*s=NULL;
  3130.               current_local_var_offset = 0;>>
  3131.             WORD
  3132.             <<zzs_scope(&globals);
  3133.               var = zzs_newadd($1.text);
  3134.               var->level = GLOBAL;
  3135.               var->token = FUNC;
  3136.             >>
  3137.             "\(" (  def[&locals, PARAMETER] <<parm=#1;>>
  3138.                  |  <<current_local_var_offset = 1;>>
  3139.                  )
  3140.             "\)"
  3141.             "\{"
  3142.                 ( "var" def[&locals, LOCAL]
  3143.                   <<if ( v==NULL ) v = #2; else v = #(NULL,v,#2);>>
  3144.                   ";"
  3145.                 )*
  3146.                 ( statement
  3147.                   <<if ( s==NULL ) s = #1; else s = #(NULL,s,#1);>>
  3148.                 )*
  3149.             "\}"
  3150.             <<s = #(#[SLIST], s);
  3151.               v = #(#[DefineVar], v);
  3152.               parm = #(#[DefineVar], parm);
  3153.               f = #(#[DefineFunc], #[FUNC,$1.text], parm, v, s);
  3154.               gen(f,DONT_CARE); printf("\n"); zzfree_ast(f);
  3155.               p = zzs_rmscope(&locals);>>
  3156.         ;
  3157.  
  3158.  
  3159.  
  3160.  
  3161.                                                                Page 51
  3162.  
  3163. PCCTS Advanced Tutorial 1.0x
  3164.  
  3165.  
  3166.  
  3167. statement!: <<AST *s=NULL, *el=NULL;>>
  3168.             expr ";"                            <<#0 = #1;>>
  3169.         |   "\{"
  3170.                 ( statement
  3171.                   <<if ( s==NULL ) s = #1; else s = #(NULL,s,#1);>>
  3172.                 )*
  3173.             "\}"                                <<#0 = #(#[SLIST], s);>>
  3174.         |   "if" "\(" expr "\)" statement
  3175.             {"else" statement <<el=#2;>>}       <<#0 = #(#[If], #3, #5, el);>>
  3176.         |   "while" "\(" expr "\)" statement    <<#0 = #(#[While], #3, #5);>>
  3177.         |   "return" expr ";"                   <<#0 = #(#[Return], #2);>>
  3178.         |   "print" expr ";"                    <<#0 = #(#[Print], #2);>>
  3179.         ;
  3180.  
  3181. expr    :   VAR "="^ expr
  3182.         |   expr0
  3183.         ;
  3184.  
  3185. expr0   :   expr1 ( (   "=="^
  3186.                     |   "!="^
  3187.                     )
  3188.                     expr1
  3189.                   )*
  3190.         ;
  3191.  
  3192. expr1   :   expr2 ( (   "\+"^
  3193.                     |   "\-"^
  3194.                     )
  3195.                     expr2
  3196.                   )*
  3197.         ;
  3198.  
  3199. expr2   :   expr3 ( (   "\*"^
  3200.                     |   "/"^
  3201.                     )
  3202.                     expr3
  3203.                   )*
  3204.         ;
  3205.  
  3206.  
  3207.  
  3208.  
  3209.  
  3210.  
  3211.  
  3212.  
  3213.  
  3214.  
  3215.  
  3216.  
  3217.  
  3218.  
  3219.  
  3220.  
  3221.  
  3222.  
  3223.                                                                Page 52
  3224.  
  3225. PCCTS Advanced Tutorial 1.0x
  3226.  
  3227.  
  3228.  
  3229. expr3   :   { "\-"^ } expr4
  3230.         ;
  3231.  
  3232. expr4!  :   <<AST *f=NULL, *arg=NULL;>>
  3233.             STRING          <<#0 = #[STRING, $1.text];>>
  3234.         |   VAR             <<#0 = #[VAR, $1.text];>>
  3235.         |   (   FUNC        <<f  = #[FUNC, $1.text];>>
  3236.             |   WORD        <<f  = #[FUNC, $1.text];>>
  3237.             )
  3238.             "\(" { expr <<arg=#1;>> } "\)"
  3239.             <<#0 = #(f, arg);>>
  3240.         |   "\(" expr "\)"  <<#0 = #2;>>
  3241.         ;
  3242.  
  3243. #token WORD "[a-zA-Z]+"
  3244.     <<{
  3245.         Sym *p = zzs_get(LATEXT(1));
  3246.         if ( p != NULL ) NLA = p->token;
  3247.     }>>
  3248.  
  3249.  
  3250.  
  3251. 4.3.  Example translations
  3252.  
  3253.      To illustrate how functions get translated, consider the  follow-
  3254. ing sc program:
  3255.  
  3256.  
  3257. var a;
  3258.  
  3259. main(n)
  3260. {
  3261.     var b;
  3262. }
  3263.  
  3264.  
  3265.  
  3266. Our translator would create trees represented by:
  3267.  
  3268.  
  3269.  ( DefineVar WORD )
  3270.  ( DefineFunc FUNC ( DefineVar WORD ) ( DefineVar WORD ) SLIST )
  3271.  
  3272.  
  3273.  
  3274. where WORD represents the variables found on the input stream.   SLIST
  3275. has no child because there were no statements in the function.
  3276.  
  3277.      Some example statement transformations follow.
  3278.  
  3279. if:
  3280.  
  3281.  
  3282.  
  3283.  
  3284.  
  3285.                                                                Page 53
  3286.  
  3287. PCCTS Advanced Tutorial 1.0x
  3288.  
  3289.  
  3290.  
  3291. if ( b == "hello" ) print n;
  3292.  
  3293.  
  3294.  
  3295. translates to
  3296.  
  3297.  
  3298. ( If ( Equal b "hello" ) ( Print n ) )
  3299.  
  3300.  
  3301.  
  3302. while:
  3303.  
  3304.  
  3305. while ( i != "10" ) { print i; i = i+"1"; }
  3306.  
  3307.  
  3308.  
  3309. translates to
  3310.  
  3311.  
  3312. ( While ( NotEqual i "10" ) ( SLIST ( Print i ) ( = i ( Add i "1" ) ) ) )
  3313.  
  3314.  
  3315.  
  3316.      Expressions have the operator at the root  and  the  operands  as
  3317. children.  For example,
  3318.  
  3319.  
  3320. i = a + "3" * "9" + f("jim");
  3321.  
  3322.  
  3323.  
  3324. would be translated to:
  3325.  
  3326.  
  3327. ( = i ( Add ( Add a ( Mul "3" "9" ) ) ( f "jim" ) ) )
  3328.  
  3329.  
  3330.  
  3331. which looks like:
  3332.  
  3333.  
  3334.  
  3335.  
  3336.  
  3337.  
  3338.  
  3339.  
  3340.  
  3341.  
  3342.  
  3343.  
  3344.  
  3345.  
  3346.  
  3347.                                                                Page 54
  3348.  
  3349. PCCTS Advanced Tutorial 1.0x
  3350.  
  3351.  
  3352.  
  3353.         =
  3354.         |
  3355.         v
  3356.         i -> Add
  3357.               |
  3358.               v
  3359.              Add --------------> f
  3360.               |                  |
  3361.               v                  v
  3362.               a -> Mul         "jim"
  3363.                     |
  3364.                     v
  3365.                    "3" -> "9"
  3366.  
  3367.  
  3368.  
  3369. 5.  Code generation from intermediate form
  3370.  
  3371.      To translate  the  intermediate  form  (IF)  to  the  stack  code
  3372. described  above,  we present the following simple little code genera-
  3373. tor.  We use no devious C programming  to  make  this  fast  or  nifty
  3374. because this document concentrates on how PCCTS grammars are developed
  3375. not on how to write spectacular C code.
  3376.  
  3377. 5.1.  Modification of tree construction grammar
  3378.  
  3379.      To convert from the translator above that printed  out  trees  in
  3380. lisp  format,  we add the following definitions needed as arguments to
  3381. gen() in the #header action.
  3382.  
  3383.  
  3384.           #define DONT_CARE         0
  3385.           #define SIDE_EFFECTS      1
  3386.           #define VALUE             2
  3387.  
  3388.  
  3389.  
  3390.      Also,  we  replace  all  calls  to  lisp(tree)   with   gen(tree,
  3391. DONT_CARE).
  3392.  
  3393. 5.2.  Code generator
  3394.  
  3395.      Function gen() presented below accepts an AST as an argument  and
  3396. walks  the tree generating output when necessary.  You will notice all
  3397. the header information needed by this file, code.c.  This  illustrates
  3398. one  of  the  minor inconveniences of PCCTS.  Any C file that needs to
  3399. access PCCTS variables, rules, etc... must include all of  the  things
  3400. that PCCTS generates at the head of all PCCTS generated files.
  3401.  
  3402.      The code generator accepts an evaluation mode argument so that it
  3403. can remove some unnecessary code.  For example,
  3404.  
  3405.  
  3406.  
  3407.  
  3408.  
  3409.                                                                Page 55
  3410.  
  3411. PCCTS Advanced Tutorial 1.0x
  3412.  
  3413.  
  3414.  
  3415. main()
  3416. {
  3417.     "3" + f();
  3418. }
  3419. f()
  3420. {}
  3421.  
  3422.  
  3423.  
  3424. would result in
  3425.  
  3426.  
  3427. #include "sc.h"
  3428. _main()
  3429. {
  3430.     BEGIN;
  3431.     CALL(f);
  3432.     POP;
  3433.     END;
  3434. }
  3435.  
  3436. f()
  3437. {
  3438.     BEGIN;
  3439.     END;
  3440. }
  3441.  
  3442.  
  3443.  
  3444. Code to push and add  "3"  was  eliminated  because  it  had  no  side
  3445. effects.  Only function calls have side effects in sc.
  3446.  
  3447.  
  3448.  
  3449.  
  3450.  
  3451.  
  3452.  
  3453.  
  3454.  
  3455.  
  3456.  
  3457.  
  3458.  
  3459.  
  3460.  
  3461.  
  3462.  
  3463.  
  3464.  
  3465.  
  3466.  
  3467.  
  3468.  
  3469.  
  3470.  
  3471.                                                                Page 56
  3472.  
  3473. PCCTS Advanced Tutorial 1.0x
  3474.  
  3475.  
  3476.  
  3477. /*
  3478.  * Simple code generator for PCCTS 1.0x tutorial
  3479.  *
  3480.  * Terence Parr
  3481.  * Purdue University
  3482.  * Electrical Engineering
  3483.  * March 19, 1992
  3484.  */
  3485. #include <stdio.h>
  3486. #include "sym.h"
  3487. #include "charbuf.h"
  3488. #define AST_FIELDS int token, level, offset; char str[D_TextSize];
  3489. #define zzcr_ast(ast,attr,tok,text) create_ast(ast,attr,tok,text)
  3490. #include "antlr.h"
  3491. #include "ast.h"
  3492. #include "tokens.h"
  3493. #include "dlgdef.h"
  3494. #include "mode.h"
  3495. #define GLOBAL              0
  3496. #define PARAMETER           1
  3497. #define LOCAL               2
  3498.  
  3499.  
  3500.  
  3501.  
  3502. static int LabelNum=0, GenHeader=0;
  3503.  
  3504. #define DONT_CARE                       0
  3505. #define SIDE_EFFECTS            1
  3506. #define VALUE                           2
  3507.  
  3508.  
  3509.  
  3510.  
  3511. gen(t,emode)
  3512. AST *t;
  3513. int emode;      /* evaluation mode member { SIDE_EFFECTS, VALUE, DONT_CARE } */
  3514. {
  3515.         AST *func, *arg, *locals, *slist, *a, *opnd1, *opnd2, *lhs, *rhs;
  3516.         int n;
  3517.  
  3518.  
  3519.  
  3520.  
  3521.         if ( t == NULL ) return;
  3522.         if ( !GenHeader ) { printf("#include \"sc.h\"\n"); GenHeader=1; }
  3523.  
  3524.         switch ( t->token )
  3525.         {
  3526.  
  3527.  
  3528.  
  3529.  
  3530.  
  3531.  
  3532.  
  3533.                                                                Page 57
  3534.  
  3535. PCCTS Advanced Tutorial 1.0x
  3536.  
  3537.  
  3538.  
  3539.         case DefineFunc :
  3540.                 func = zzchild(t);
  3541.                 arg = zzchild( zzsibling(func) );
  3542.                 locals = zzchild( zzsibling( zzsibling(func) ) );
  3543.                 slist = zzsibling( zzsibling( zzsibling(func) ) );
  3544.                 if ( strcmp(func->str, "main") == 0 )
  3545.                         printf("_%s()\n{\n\tBEGIN;\n", func->str);
  3546.                 else
  3547.                         printf("%s()\n{\n\tBEGIN;\n", func->str);
  3548.                 for (a=locals; a!=NULL; a = zzsibling(a)) printf("\tLOCAL;\n");
  3549.                 gen( slist, DONT_CARE );
  3550.                 printf("\tEND;\n}\n");
  3551.                 break;
  3552.  
  3553.  
  3554.  
  3555.  
  3556.         case SLIST :
  3557.                 for (a=zzchild(t); a!=NULL; a = zzsibling(a))
  3558.                 {
  3559.                         gen( a, EvalMode(a->token) );
  3560.                         if ( a->token == Assign ) printf("\tPOP;\n");
  3561.                 }
  3562.                 break;
  3563.  
  3564.  
  3565.  
  3566.  
  3567.         case DefineVar :
  3568.                 printf("SCVAR %s;\n", zzchild(t)->str);
  3569.                 break;
  3570.  
  3571.  
  3572.  
  3573.  
  3574.  
  3575.  
  3576.  
  3577.  
  3578.  
  3579.  
  3580.  
  3581.  
  3582.  
  3583.  
  3584.  
  3585.  
  3586.  
  3587.  
  3588.  
  3589.  
  3590.  
  3591.  
  3592.  
  3593.  
  3594.  
  3595.                                                                Page 58
  3596.  
  3597. PCCTS Advanced Tutorial 1.0x
  3598.  
  3599.  
  3600.  
  3601.         case Mul :
  3602.         case Div :
  3603.         case Add :
  3604.         case Sub :
  3605.         case Equal :
  3606.         case NotEqual :
  3607.                 opnd1 = zzchild(t);
  3608.                 opnd2 = zzsibling( opnd1 );
  3609.                 gen( opnd1, emode );
  3610.                 gen( opnd2, emode );
  3611.                 if ( emode == SIDE_EFFECTS ) break;
  3612.                 switch ( t->token )
  3613.                 {
  3614.                 case Mul : printf("\tMUL;\n"); break;
  3615.                 case Div : printf("\tDIV;\n"); break;
  3616.                 case Add : printf("\tADD;\n"); break;
  3617.                 case Sub : if ( opnd2==NULL ) printf("\tNEG;\n");
  3618.                                    else printf("\tSUB;\n");
  3619.                                    break;
  3620.                 case Equal : printf("\tEQ;\n"); break;
  3621.                 case NotEqual : printf("\tNEQ;\n"); break;
  3622.                 }
  3623.                 break;
  3624.  
  3625.  
  3626.  
  3627.  
  3628.         case If :
  3629.                 a = zzchild(t);
  3630.                 gen( a, VALUE );                                /* gen code for expr */
  3631.                 n = LabelNum++;
  3632.                 printf("\tBRF(iflabel%d);\n", n);
  3633.                 a = zzsibling(a);
  3634.                 gen( a, EvalMode(a->token) );   /* gen code for statement */
  3635.                 printf("iflabel%d: ;\n", n);
  3636.                 break;
  3637.  
  3638.  
  3639.  
  3640.  
  3641.         case While :
  3642.                 a = zzchild(t);
  3643.                 n = LabelNum++;
  3644.                 printf("wbegin%d: ;\n", n);
  3645.                 gen( a, VALUE );                                /* gen code for expr */
  3646.                 printf("\tBRF(wend%d);\n", n);
  3647.                 a = zzsibling(a);
  3648.                 gen( a, EvalMode(a->token) );   /* gen code for statement */
  3649.                 printf("\tBR(wbegin%d);\n", n);
  3650.                 printf("wend%d: ;\n", n);
  3651.                 break;
  3652.  
  3653.  
  3654.  
  3655.  
  3656.  
  3657.                                                                Page 59
  3658.  
  3659. PCCTS Advanced Tutorial 1.0x
  3660.  
  3661.  
  3662.  
  3663.    case Return :
  3664.                 gen( zzchild(t), VALUE );
  3665.                 printf("\tRETURN;\n");
  3666.                 break;
  3667.  
  3668.  
  3669.  
  3670.  
  3671.         case Print :
  3672.                 gen( zzchild(t), VALUE );
  3673.                 printf("\tPRINT;\n");
  3674.                 break;
  3675.  
  3676.  
  3677.  
  3678.  
  3679.         case Assign :
  3680.                 lhs = zzchild(t);
  3681.                 rhs = zzsibling( lhs );
  3682.                 gen( rhs, emode );
  3683.                 printf("\tDUP;\n");
  3684.                 if ( lhs->level == GLOBAL ) printf("\tSTORE(%s);\n", lhs->str);
  3685.                 else printf("\tLSTORE(%d);\n", lhs->offset);
  3686.                 break;
  3687.  
  3688.  
  3689.  
  3690.  
  3691.         case VAR :
  3692.                 if ( emode == SIDE_EFFECTS ) break;
  3693.                 if ( t->level == GLOBAL ) printf("\tPUSH(%s);\n", t->str);
  3694.                 else printf("\tLPUSH(%d);\n", t->offset);
  3695.                 break;
  3696.  
  3697.  
  3698.  
  3699.  
  3700.         case FUNC :
  3701.                 gen( zzchild(t), VALUE );
  3702.                 printf("\tCALL(%s);\n", t->str);
  3703.                 break;
  3704.  
  3705.  
  3706.  
  3707.  
  3708.         case STRING :
  3709.                 if ( emode == SIDE_EFFECTS ) break;
  3710.                 printf("\tSPUSH(%s);\n", t->str);
  3711.                 break;
  3712.  
  3713.  
  3714.  
  3715.  
  3716.  
  3717.  
  3718.  
  3719.                                                                Page 60
  3720.  
  3721. PCCTS Advanced Tutorial 1.0x
  3722.  
  3723.  
  3724.  
  3725.         default :
  3726.                 printf("Don't know how to handle: %s\n", zztokens[t->token]);
  3727.                 break;
  3728.         }
  3729. }
  3730.  
  3731.  
  3732.  
  3733.  
  3734. EvalMode( tok )
  3735. int tok;
  3736. {
  3737.         if ( tok == Assign || tok == If || tok == While ||
  3738.                  tok == Print || tok == Return ) return VALUE;
  3739.         else return SIDE_EFFECTS;
  3740. }
  3741.  
  3742.  
  3743.  
  3744. 5.3.  Makefile for code generator
  3745.  
  3746.      This makefile is roughly the same as before except that  we  need
  3747. to  tell PCCTS to generate tree information and we need to link in the
  3748. code generator.
  3749.  
  3750.  
  3751. CFLAGS= -I../h
  3752. GRM=tut4
  3753. SRC=scan.c $(GRM).c err.c sym.c code.c
  3754. OBJ=scan.o $(GRM).o err.o sym.o code.o
  3755.  
  3756. tutorial: $(OBJ) $(SRC)
  3757.     cc -o $(GRM) $(OBJ)
  3758.  
  3759. $(GRM).c parser.dlg : $(GRM).g
  3760.     antlr -k 2 -gt $(GRM).g
  3761.  
  3762. scan.c : parser.dlg
  3763.     dlg -C2 parser.dlg scan.c
  3764.  
  3765.  
  3766.  
  3767.  
  3768.  
  3769.  
  3770.  
  3771.  
  3772.  
  3773.  
  3774.  
  3775.  
  3776.  
  3777.  
  3778.  
  3779.  
  3780.  
  3781.                                                                Page 61
  3782.  
  3783.  
  3784.  
  3785.  
  3786.  
  3787.  
  3788.  
  3789.                           Table of Contents
  3790.  
  3791.  
  3792.  
  3793.  
  3794. 1. sc Language definition .......................................    2
  3795.  
  3796.          1.1. sc Expressions ....................................    2
  3797.  
  3798.          1.2. sc Functions and statements .......................    2
  3799.  
  3800.          1.3. Example ...........................................    3
  3801.  
  3802. 2. Language recognition .........................................    3
  3803.  
  3804.          2.1. Lexical analysis ..................................    4
  3805.  
  3806.          2.2. Attributes ........................................    4
  3807.  
  3808.          2.3. Grammatical analysis ..............................    5
  3809.  
  3810.                   2.3.1. Definitions, variables .................    5
  3811.  
  3812.                   2.3.2. Functions ..............................    5
  3813.  
  3814.                   2.3.3. Statements .............................    6
  3815.  
  3816.                   2.3.4. Expressions ............................    6
  3817.  
  3818.          2.4. Complete ANTLR description (w/o symbol table
  3819. management) .....................................................    8
  3820.  
  3821.          2.5. Makefile ..........................................   10
  3822.  
  3823.          2.6. Testing ...........................................   10
  3824.  
  3825.          2.7. Symbol table management ...........................   10
  3826.  
  3827.          2.8. Complete ANTLR description (with symbol table
  3828. management) .....................................................   15
  3829.  
  3830.          2.9. File sym.h ........................................   18
  3831.  
  3832.          2.10. Makefile (for use with symbol table management)
  3833.  
  3834.          2.11. Sample input/output ..............................   20
  3835.  
  3836. 3. Translate sc to stack code ...................................   21
  3837.  
  3838.          3.1. A simple stack machine for sc .....................   21
  3839.  
  3840.  
  3841.  
  3842.  
  3843.  
  3844.  
  3845.  
  3846.  
  3847.  
  3848.                   3.1.1. Functions ..............................   22
  3849.  
  3850.                   3.1.2. Variables ..............................   23
  3851.  
  3852.                   3.1.3. Expressions ............................   24
  3853.  
  3854.                   3.1.4. Instructions ...........................   26
  3855.  
  3856.          3.2. Examples ..........................................   27
  3857.  
  3858.          3.3. Augmenting grammar to dump stack code .............   28
  3859.  
  3860.          3.4. Full translator ...................................   30
  3861.  
  3862.          3.5. Makefile for Full Translator ......................   35
  3863.  
  3864.          3.6. Use of translator .................................   35
  3865.  
  3866.          3.7. Stack code macros - sc.h ..........................   36
  3867.  
  3868. 4. Intermediate form construction ...............................   40
  3869.  
  3870.          4.1. Tree Construction .................................   40
  3871.  
  3872.          4.2. Full Grammar to Construct Trees ...................   47
  3873.  
  3874.          4.3. Example translations ..............................   53
  3875.  
  3876. 5. Code generation from intermediate form .......................   55
  3877.  
  3878.          5.1. Modification of tree construction grammar .........   55
  3879.  
  3880.          5.2. Code generator ....................................   55
  3881.  
  3882.          5.3. Makefile for code generator .......................   61
  3883.  
  3884.  
  3885.  
  3886.  
  3887.  
  3888.  
  3889.  
  3890.  
  3891.  
  3892.  
  3893.  
  3894.  
  3895.  
  3896.  
  3897.  
  3898.  
  3899.  
  3900.  
  3901.  
  3902.  
  3903.  
  3904.  
  3905.                                                                 Page 1
  3906.  
  3907.